Dependent rounding for knapsack/partition constraints and facility location
David G. Harris, Thomas Pensyl, Aravind Srinivasan, Khoa Trinh · 2017
We develop a new dependent rounding algorithm targeting systems with a mixture of knapsack and partition constraints. Such constraint systems arise in a number of facility location problems, and we study two in particular: multi-knapsack median and multi-knapsack center. Our rounding algorithms gives new approximation and pseudo-approximation algorithms for these problems. The new dependent rounding process has two main technical advantages over previous ones. First, it gives substantial near-independence properties among the variables being rounded. These are critical for facility location problems with highly non-linear objective functions. Second, the rounding process lends itself to a new type of pseudo-approximation guarantee, which has an violation of the knapsack constraints. This is in contrast to previous algorithms which typically give $(1+\epsilon)$--multiplicative violations of these constraints. This additive violation is different from additive error; it is a more flexible notion which can be used as a technical tool to achieve new and more efficient multiplicative pseudo-approximations and even true approximation algorithms. One key technical tool we develop, which may be of independent interest, is a new tail bound analogous to Feige (2006) for sums of random variables with unbounded variances.