1 Search Results for "Qiu, Frederick"

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-dev.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}
}
  • Refine by Author
  • 1 Qiu, Frederick
  • 1 Singla, Sahil

  • Refine by Classification
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Negative Association
  • 1 Negative Dependence
  • 1 Submodular Dominance
  • 1 Submodular Optimization
  • 1 Submodular Prophet Inequality
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact