An Algorithm for the 2-Median Problem on Two-Dimensional Meshes
Francis C. M. Lau · The Computer Journal · 2001
We study the p-median problem which is one the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(mn 2 p)-time algorithm for solving the problem, where, assuming that m n, m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, and p the number of demand points. 1 Introduction The mesh (and its variant, the torus) is a popular topology for processor interconnection in parallel computers. It has practical advantages such as low degree and perfectly compact layout when compared to other well-known topologies, for example the hypercube. A notable example of parallel computers based on the mesh topology is the iWarp system [4]. Dally has shown that low-dimensional networks have lower latency and higher hot-spot throughput than high-dimensional networks [2]. In this paper, we study the problem of finding a 2-median set in a two-dimensional mesh. The p-median problem is a well-known problem ...