An approximation solution for the 2-median problem on two-dimensional meshes

We study the p-median problem which is one of the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(m² + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5 + δ on the communication cost, where m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, m ≥ n,q the number of demand points, and δ is some positive constant which can be as small as needed.