Survey on approximation algorithms for the k-median problem

The $k$-median problem is one of the classical topics in the fields of theoretical computer science and combinatorial optimization, which is widely applied to image processing, pattern recognition, supply chain management, and data mining. Nowadays, with the development of big data and machine learning techniques, the practical applications of the $k$-median problem become more and more complex. This leads to a variety of new research topics that need to be solved urgently. In this paper, we introduce effective algorithms based on linear programming rounding, primal-dual, dual-fitting, local search, Lagrange relaxation, and other techniques for the classical $k$-median problem and its variants. We begin with the close relation between the $k$-median problem and the uncapacitated facility location problem. Then we introduce several important variants of the $k$-median problem including the $k$-center problem, $k$-facility location problem, knapsack median problem, fault-tolerant $k$-median problem, capacitated $k$-median problem, $k$-median problem with lower bounds, $k$-median problem with penalties, $k$-median problem with outliers, and online median problem. Finally, we survey the approximation algorithms for the $k$-median problem and propose several open problems in this area.