Premium
The two‐median problem on Manhattan meshes
Author(s) -
Golin Mordecai J.,
Zhang Yan
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20156
Subject(s) - polygon mesh , combinatorics , mathematics , independent and identically distributed random variables , metric (unit) , binary logarithm , row , algorithm , space (punctuation) , discrete mathematics , computer science , random variable , geometry , statistics , operations management , database , economics , operating system
Abstract 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