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/sup 2/ + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5 + /spl delta/ on the communication cost, where m is the nu...

Full description

Saved in:
Bibliographic Details
Main Authors: Tse, S.S.H., Lau, F.C.M.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Computer networks
Computer science
Concurrent computing
Costs
distributed and parallel computing
Distributed computing
Hypercubes
location problem
mesh
Network topology
P-median
parallel computers
Parallel processing
Tree graphs
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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/sup 2/ + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5 + /spl delta/ 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 /spl ges/ n,q the number of demand points, and /spl delta/ is some positive constant which can be as small as needed.
ISSN:1550-445X
2332-5658
DOI:10.1109/AINA.2005.92