The k-median problem is a classical clustering problem in which the goal is to select a set \(S \subseteq V\) of k nodes in a given weighted graph \(G=(V,E)\) , so as to minimize the sum of distances from each node in \(V\setminus S\) to its nearest node in S. The nodes in S are called facilities, and the remaining nodes are clients; a solution for the problem naturally partitions the nodes of the graph into k clusters, where each cluster has one facility. We assume that the edge lengths satisfy the triangle inequality. We present an asymmetric resonance neural network for solving the k-median problem. The network consists of 2 layers of neurons encoding assignments of clients to clusters and selections of facilities for clusters. We present an efficient implementation of the algorithm that outperforms other known local search and neural network-based algorithms for the k-median problem. Furthermore, we show that a modification of our neural network leads to an approximation algorithm with the same approximation ratio as a local search algorithm by Arya et al. (STOC 2001).