Structural iterative rounding for generalized k-median problems

• 成果类型: Article
• 署名作者: Gupta, Anupam; Moseley, Benjamin; Zhou, Rudy
• 署名单位: New York University; Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02119-7
• 发表日期: 2025
• 页码: 581-634
• 关键词: Facility location; algorithms

摘要

This paper considers approximation algorithms for generalized k-median problems. This class of problems can be informally described as k-median with a constant number of extra constraints, and includes k-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized k-median that outputs a 6.387-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for k-median with outliers. The main technical innovation is allowing richer constraint sets in the iterative rounding and taking advantage of the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for k-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios 6.994+& varepsilon; and 6.387+& varepsilon; for k-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio 7.081+& varepsilon; for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACMSIGACT Symposium on Theory of Computing, 2018).