Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/18755

The two-median problem on Manhattan meshes

Authors Golin, Mordecai J. View this author's profile
Zhang, Yan HKUST affiliated (currently or previously)
Issue Date 2007
Source Networks , v. 49, (3), 2007, MAY, p. 226-233
Summary 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(MN) space. One is an O(MN2) time algorithm, while the other is an algorithm running in O(MN log N) time with high probability and in O(MN2) 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. (c) 2007 Wiley Periodicals, Inc.
Subjects
ISSN 0028-3045
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST