In submodular optimization we often deal with the expected value of a submodular function $f$ on a distribution $\mathcal{D}$ over sets of elements. In this work we study such submodular expectations for negatively dependent distributions. We introduce a natural notion of negative dependence, which we call Weak Negative Regression (WNR), that generalizes both Negative Association and Negative Regression. We observe that WNR distributions satisfy Submodular Dominance, whereby the expected value of $f$ under $\mathcal{D}$ is at least the expected value of $f$ under a product distribution with the same element-marginals. Next, we give several applications of Submodular Dominance to submodular optimization. In particular, we improve the best known submodular prophet inequalities, we develop new rounding techniques for polytopes of set systems that admit negatively dependent distributions, and we prove existence of contention resolution schemes for WNR distributions.
翻译:在亚模块优化中,我们经常处理一个子模块函数的预期值($ff$) 。 在这项工作中,我们研究了对负依赖性分布的这种亚模块期望值。 我们引入了一种自然的负依赖性概念,我们称之为弱负负回归(WNR),它概括了负关联和负回归。我们观察到,WNR的分布满足了子模块的主导性,根据此,在以相同元素边际分配的产品中,预期值($mathcal{D}$)至少为$f$的预期值。接下来,我们给亚模块优化提供了几种子模块主导性应用。特别是,我们改进了已知的最佳子模块先知不平等,我们开发了接受负依赖性分布的设定系统多端的新的圆形技术,我们证明存在用于WNR分布的争议解决方案。