The two‐median problem on Manhattan meshes

We investigate the two‐median problem on a mesh with M columns and N rows ( M ≥ N ), under the Manhattan ( L 1 ) metric. We derive exact algorithms with respect to m , n , and r , the number of columns, rows, and vertices, respectively, that contain requests. Specifically, we give an O ( mn 2 log m ) time, O ( r ) space algorithm for general (nonuniform) meshes (assuming m ≥ n ). For uniform meshes, we give two algorithms both using O ( M N ) space. One is an O ( MN 2 ) time algorithm, while the other is an algorithm running in O ( MN log N ) time with high probability and in O ( MN 2 ) time in the worst case assuming the weights are independent and identically distributed random variables satisfying certain natural conditions. These improve upon the previously best‐known algorithm that runs in O ( mn 2 r ) time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 226–233 2007