Simpler Algorithms for Capacitated $k$-Median with $(1 + ε)$-Violations Using New Inequalities

We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+ε)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_ε(1)$-approximation with $(1+ε)$-violations via complex extended configuration linear programm