Loading...
Approximation Algorithms for Geometric Median Problems
Lin, Jyh-Han Vitter, Jeffrey Scott
Lin, Jyh-Han
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
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.
Description
Date
1992
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Research Projects
Organizational Units
Journal Issue
Keywords
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