Simpler Algorithms for Capacitated $k$-Median with $(1 + \epsilon)$-Violations Using New Inequalities
We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+\epsilon)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_\epsilon(1)$-approximation with $(1+\epsilon)$-violations via complex extended configuration linear program...