%0 Journal Article
%T An improved approximation algorithm for k-median problem using a new factor-revealing LP
%A Chenchen Wu
%A Dachuan Xu
%A Donglei Du
%A Yishui Wang
%J Computer Science
%D 2014
%I arXiv
%X 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+\epsilon (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 +\epsilon based on a new (1, 1.93910094) bi-factor approximation algorithm for the FLP.
%U http://arxiv.org/abs/1410.4161v2