An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization

Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki +2

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However,…