Skip to main content

A Dependent LP-Rounding Approach for the k-Median Problem

Author(s): Charikar, Moses; Li, Shi

To refer to this page use:
Abstract: In this paper, we revisit the classical k-median problem. Using the standard LP relaxation for k-median, we give an efficient algorithm to construct a probability distribution on sets of k centers that matches the marginals specified by the optimal LP solution. Analyzing the approximation ratio of our algorithm presents significant technical difficulties: we are able to show an upper bound of 3.25. While this is worse than the current best known 3 + ε guarantee of [2], because: (1) it leads to 3.25 approximation algorithms for some generalizations of the k-median problem, including the k-facility location problem introduced in [10], (2) our algorithm runs in 𝑂̃ (𝑘3𝑛2/𝛿2) time to achieve 3.25(1 + δ)-approximation compared to the O(n 8) time required by the local search algorithm of [2] to guarantee a 3.25 approximation, and (3) our approach has the potential to beat the decade old bound of 3 + ε for k-median. We also give a 34-approximation for the knapsack median problem, which greatly improves the approximation constant in [13]. Using the same technique, we also give a 9-approximation for matroid median problem introduced in [11], improving on their 16-approximation.
Publication Date: 2012
Citation: Charikar, Moses, and Shi Li. "A Dependent LP-Rounding Approach for the k-Median Problem." Automata, Languages, and Programming (2012): 194-205. doi:10.1007/978-3-642-31594-7_17
DOI: 10.1007/978-3-642-31594-7_17
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 194 - 205
Type of Material: Conference Article
Series/Report no.: Lecture Notes in Computer Science;7391
Journal/Proceeding Title: Automata, Languages, and Programming
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.