DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.44

Submodular Dominance and Applications

Authors: Frederick Qiu and Sahil Singla

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

In submodular optimization we often deal with the expected value of a submodular function f on a distribution 𝒟 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 𝒟 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.

Cite as

Frederick Qiu and Sahil Singla. Submodular Dominance and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 44:1-44:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{qiu_et_al:LIPIcs.APPROX/RANDOM.2022.44,
  author =	{Qiu, Frederick and Singla, Sahil},
  title =	{{Submodular Dominance and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{44:1--44:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.44},
  URN =		{urn:nbn:de:0030-drops-171666},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.44},
  annote =	{Keywords: Submodular Optimization, Negative Dependence, Negative Association, Weak Negative Regression, Submodular Dominance, Submodular Prophet Inequality}
}

Search Results

Documents authored by Qiu, Frederick

Submodular Dominance and Applications

Abstract

Cite as

Thanks for your feedback!

Could not send message