2026-07-21T02:34:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14146 2024-03-06T10:53:35Z ddc:004 open_access

Structural Iterative Rounding for Generalized k-Median Problems Gupta, Anupam Moseley, Benjamin Zhou, Rudy approximation algorithms clustering linear programming 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 is based on iteratively rounding linear programs, and the main technical innovation comes from understanding the rich 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 + ε and 6.387 + ε for k-median with outliers and knapsack median, respectively. These both improve on the best known approximations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Gupta and Benjamin Moseley and Rudy Zhou 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.77 urn:nbn:de:0030-drops-141465 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.77 eng https://creativecommons.org/licenses/by/4.0/legalcode