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

Understand

Dependent rounding is a useful technique for optimization problems with hard budget constraints.

• This framework naturally leads to \emph{negative correlation} properties.
• However, what if an application naturally calls for dependent rounding on the one hand, and desires \emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables.
• The recent breakthrough of Li & Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly.