Concentration of Submodular Functions Under Negative Dependence
share
We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, resolving an open problem raised in (<cit.>). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms (<cit.>). We discuss some applications of our results to combinatorial optimization and beyond.
READ FULL TEXT