License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.3
URN: urn:nbn:de:0030-drops-112188
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11218/
Go to the corresponding LIPIcs Volume Portal

Moseley, Benjamin ; Sviridenko, Maxim

Submodular Optimization with Contention Resolution Extensions

pdf-format:
LIPIcs-APPROX-RANDOM-2019-3.pdf (0.6 MB)

Abstract

This paper considers optimizing a submodular function subject to a set of downward closed constraints. Previous literature on this problem has often constructed solutions by (1) discovering a fractional solution to the multi-linear extension and (2) rounding this solution to an integral solution via a contention resolution scheme. This line of research has improved results by either optimizing (1) or (2).
Diverging from previous work, this paper introduces a principled method called contention resolution extensions of submodular functions. A contention resolution extension combines the contention resolution scheme into a continuous extension of a discrete submodular function. The contention resolution extension can be defined from effectively any contention resolution scheme. In the case where there is a loss in both (1) and (2), by optimizing them together, the losses can be combined resulting in an overall improvement. This paper showcases the concept by demonstrating that for the problem of optimizing a non-monotone submodular subject to the elements forming an independent set in an interval graph, the algorithm gives a .188-approximation. This improves upon the best known 1/(2e)~eq .1839 approximation.

BibTeX - Entry

@InProceedings{moseley_et_al:LIPIcs:2019:11218,
  author =	{Benjamin Moseley and Maxim Sviridenko},
  title =	{{Submodular Optimization with Contention Resolution Extensions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11218},
  URN =		{urn:nbn:de:0030-drops-112188},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.3},
  annote =	{Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling}
}

Keywords: Submodular, Optimization, Approximation Algorithm, Interval Scheduling
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

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