Tech Report CS-92-37
Approximation Algorithms for Geometric Median Problems
Jyh-Han Lin and Jeffrey Scott Vitter
In this paper we present approximation algorithms for median problems in metric spaces and fixed-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 transformation technique is fundamentally different from the methods of randomized and deterministic rounding in the literature 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.