Tech Report CS-92-37

Approximation Algorithms for Geometric Median Problems

Jyh-Han Lin and Jeffrey Scott Vitter

August 1992


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.

(complete text in pdf or gzipped postscript)