19th International Conference on Advanced Information Networking and Applications (AINA'05) Volume 2 (INA,, USW,, WAMIS,, and IPv6 papers) An Approximation Solution for the 2-Median Problem on Two-Dimensional Meshes Taipei, Taiwan March 25-March 30 ISBN: 0-7695-2249-1
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/AINA.2005.92
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 0(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 6 is some positive constant which can be as small as needed.
Index Terms:
P-median, location problem, approximation algorithms, mesh, parallel computers, distributed and parallel computing
Citation:
Savio S.H. Tse, Francis C.M. Lau, "An Approximation Solution for the 2-Median Problem on Two-Dimensional Meshes," aina, vol. 2, pp.457-460, 19th International Conference on Advanced Information Networking and Applications (AINA'05) Volume 2 (INA,, USW,, WAMIS,, and IPv6 papers), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb