A \({(2+\varepsilon )}\)-Approximation Algorithm for Metric \({k}\)-Median

Abstract

Abstract. In the classical NP-hard (metric) [Formula: see text]-median problem, we are given a set of [Formula: see text] clients and centers with metric distances between them, along with an integer parameter [Formula: see text]. The objective is to select a subset of [Formula: see text] open centers that minimizes the total distance from each client to its closest open center. In their seminal work, Jain, Mahdian, Markakis, Saberi, and Vazirani presented the Greedy algorithm for facility location, which implies a 2-approximation algorithm for [Formula: see text]-median that opens [Formula: see text] centers in expectation. Since then, substantial research has aimed at narrowing the gap between their algorithm and the best achievable approximation by an algorithm guaranteed to open exactly [Formula: see text] centers, as required in the [Formula: see text]-median problem. During the last decade, all improvements have been achieved by leveraging their algorithm (or a small improvement thereof), followed by a second step called bipoint rounding, which inherently adds an additional factor to the approximation guarantee. Our main result closes this gap: for any [Formula: see text], we present a [Formula: see text]-approximation algorithm for the [Formula: see text]-median problem, improving the previous best-known approximation factor of 2.613. Our approach builds on a combination of two key algorithms. First, we present a nontrivial modification of the Greedy algorithm that operates with only [Formula: see text] adaptive phases. Through a novel walk-between-solutions approach, this enables us to construct a [Formula: see text]-approximation algorithm for [Formula: see text]-median that consistently opens at most [Formula: see text] centers: via known results, this already implies a [Formula: see text]-approximation algorithm that runs in quasi-polynomial time. Second, we develop a novel [Formula: see text]-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an [Formula: see text] fraction. Achieving this involves several ideas, including a sampling approach inspired by the [Formula: see text]-means++ algorithm and a reduction to submodular optimization subject to a partition matroid. This allows us to convert the previous result into a polynomial time algorithm that opens exactly [Formula: see text] centers while maintaining the [Formula: see text]-approximation guarantee.