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.ICALP.2019.85
URN: urn:nbn:de:0030-drops-106610
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10661/
Go to the corresponding LIPIcs Volume Portal

Mizrachi, Eyal ; Schwartz, Roy ; Spoerhase, Joachim ; Uniyal, Sumedha

A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints

pdf-format:
LIPIcs-ICALP-2019-85.pdf (0.6 MB)

Abstract

Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints. We present a tight approximation algorithm that for any constant epsilon >0 achieves a guarantee of 1-(1/e)-epsilon while violating only the covering constraints by a multiplicative factor of 1-epsilon. Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints. We extend the above main result by additionally handling a matroid independence constraint as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present. Finally, we propose a novel and purely combinatorial dynamic programming approach. While this approach does not give tight bounds it yields deterministic and in some special cases also considerably faster algorithms. For example, for the well-studied special case of only packing constraints (Kulik et al. [Math. Oper. Res. `13] and Chekuri et al. [FOCS `10]), we are able to present the first deterministic non-trivial approximation algorithm. We believe our new combinatorial approach might be of independent interest.

BibTeX - Entry

@InProceedings{mizrachi_et_al:LIPIcs:2019:10661,
  author =	{Eyal Mizrachi and Roy Schwartz and Joachim Spoerhase and Sumedha Uniyal},
  title =	{{A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{85:1--85:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10661},
  URN =		{urn:nbn:de:0030-drops-106610},
  doi =		{10.4230/LIPIcs.ICALP.2019.85},
  annote =	{Keywords: submodular function, approximation algorithm, covering, packing}
}

Keywords: submodular function, approximation algorithm, covering, packing
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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