@TechReport{Dartmouth:TR99-344,
  author = {Neal E. Young},
  title = {{Greedy Approximation Algorithms for K-Medians by Randomized Rounding}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR99-344},
  year = {1999},
  month = {March},
  URL = {http://www.cs.dartmouth.edu/reports/TR99-344.ps.Z},
  abstract = {
      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.
  }
}