%T Greedy Approximation Algorithms for K-Medians by Randomized Rounding
%A Neal E. Young
%R Technical Report PCS-TR99-344
%I Dartmouth College, Computer Science
%C Hanover, NH
%D March 1999
%U http://www.cs.dartmouth.edu/reports/TR99-344.ps.Z
%X
   We give an improved approximation algorithm for the general k-medians
 problem.  Given any \epsilon>0, the algorithm finds a solution of total
 distance at most D(1+\epsilon) using at most k ln(n+n/\epsilon) medians
 (a.k.a. sites), provided some solution of total distance D using k medians
 exists.  This improves over the best previous bound (w.r.t. the number of
 medians) by a factor of \Omega(1/\epsilon) provided 1/\epsilon=n^O(1).  The
 algorithm is a greedy algorithm, derived using the method of oblivious
 randomized rounding.  It requires at most k ln(n+n/\epsilon) linear-time
 iterations.  We also derive algorithms for fractional and weighted variants
 of the problem.