A tight approximation for submodular maximization with mixed packing and covering constraints

Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase, Sumedha Uniyal

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

24 Downloads (Pure)

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 ε > 0 achieves a guarantee of 1 − 1/e − ε while violating only the covering constraints by a multiplicative factor of 1 − ε. 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.

Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771092
DOIs
Publication statusPublished - 1 Jul 2019
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Automata, Languages and Programming - Patras, Greece
Duration: 8 Jul 201912 Jul 2019
Conference number: 46

Publication series

NameLeibniz international proceedings in informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume132
ISSN (Print)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages and Programming
Abbreviated titleICALP
Country/TerritoryGreece
CityPatras
Period08/07/201912/07/2019

Keywords

  • Approximation algorithm
  • Covering
  • Packing
  • Submodular function

Fingerprint

Dive into the research topics of 'A tight approximation for submodular maximization with mixed packing and covering constraints'. Together they form a unique fingerprint.

Cite this