Approximation Algorithms for Geometric Median Problems

View/ Open
Issue Date
1992Author
Lin, Jyh-Han
Vitter, Jeffrey Scott
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
In this paper we present approximation algorithms for median problems in
metric spaces and xed-dimensional Euclidean space. Our algorithms use a new
method for transforming an optimal solution of the linear program relaxation
of the s-median problem into a provably good integral solution. This transfor-
mation technique is fundamentally di erent from the methods of randomized
and deterministic rounding [Rag, RaT] and the methods proposed in [LiV] in
the following way: Previous techniques never set variables with zero values in
the fractional solution to 1. This departure from previous methods is crucial
for the success of our algorithms.
Collections
Citation
J.-H. Lin and J. S. Vitter. “Approximation Algorithms for Geometric Median Problems,” Information Processing Letters, 44, 1992, 245–249. http://dx.doi.org/10.1016/0020-0190(92)90208-D
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.