An Improved Approximation for -median, and Positive Correlation in Budgeted Optimization
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 -median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for -median from to by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter from Li-Svensson's to .