An improved approximation algorithm for k-median problem using a new factor-revealing LP

Chenchen Wu, Dachuan Xu, Donglei Du, Yishui Wang

Abstract

The k-median problem is a well-known strongly NP-hard combinatorial optimization problem of both theoretical and practical significance. The previous best approximation ratio for this problem is 2.611+ε(Bryka et al. 2014) based on an (1, 1.95238219) bi-factor approximation algorithm for the classical facility location problem (FLP). This work offers an improved algorithm with an approximation ratio 2.592 +εbased on a new (1, 1.93910094) bi-factor approximation algorithm for the FLP.
BibTeX
@misc{wu2014improved,
  author = {Chenchen Wu and Dachuan Xu and Donglei Du and Yishui Wang},
  title = {{An improved approximation algorithm for k-median problem using a new factor-revealing LP}},
  year = {2014},
  eprint = {1410.4161},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.4161},
}

Loading related content...

Figure