Scholarlink

<p>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, partially resolving an open problem raised in ([<CitationRef CitationID="CR1">1</CitationRef>]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([<CitationRef CitationID="CR2">2</CitationRef>, <CitationRef CitationID="CR3">3</CitationRef>]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-<i>k</i> families [<CitationRef CitationID="CR4">4</CitationRef>] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [<CitationRef CitationID="CR4">4</CitationRef>].</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Concentration of Submodular Functions and Read-k Families Under Negative Dependence

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月16日

查看全文
  • Sharmila Duppala,
  • George Z. Li,
  • Juan Luque,
  • Aravind Srinivasan,
  • Renata Valieva

摘要

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, partially resolving an open problem raised in ([1]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([2, 3]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-k families [4] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [4].