License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.44
URN: urn:nbn:de:0030-drops-171666
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17166/
Go to the corresponding LIPIcs Volume Portal

Qiu, Frederick ; Singla, Sahil

Submodular Dominance and Applications

pdf-format:
LIPIcs-APPROX44.pdf (0.8 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/17166},
  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}
}

Keywords: Submodular Optimization, Negative Dependence, Negative Association, Weak Negative Regression, Submodular Dominance, Submodular Prophet Inequality
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Issue Date: 2022
Date of publication: 15.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI