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.ESA.2022.23
URN: urn:nbn:de:0030-drops-169618
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16961/
Go to the corresponding LIPIcs Volume Portal

Bodek, Kobi ; Feldman, Moran

Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case

pdf-format:
LIPIcs-ESA-2022-23.pdf (0.8 MB)

Abstract

Motivated by practical applications, recent works have considered maximization of sums of a submodular function g and a linear function ?. Almost all such works, to date, studied only the special case of this problem in which g is also guaranteed to be monotone. Therefore, in this paper we systematically study the simplest version of this problem in which g is allowed to be non-monotone, namely the unconstrained variant, which we term Regularized Unconstrained Submodular Maximization (RegularizedUSM).
Our main algorithmic result is the first non-trivial guarantee for general RegularizedUSM. For the special case of RegularizedUSM in which the linear function ? is non-positive, we prove two inapproximability results, showing that the algorithmic result implied for this case by previous works is not far from optimal. Finally, we reanalyze the known Double Greedy algorithm to obtain improved guarantees for the special case of RegularizedUSM in which the linear function ? is non-negative; and we complement these guarantees by showing that it is not possible to obtain (1/2, 1)-approximation for this case (despite intuitive arguments suggesting that this approximation guarantee is natural).

BibTeX - Entry

@InProceedings{bodek_et_al:LIPIcs.ESA.2022.23,
  author =	{Bodek, Kobi and Feldman, Moran},
  title =	{{Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16961},
  URN =		{urn:nbn:de:0030-drops-169618},
  doi =		{10.4230/LIPIcs.ESA.2022.23},
  annote =	{Keywords: Unconstrained submodular maximization, regularization, double greedy, non-oblivious local search, inapproximability}
}

Keywords: Unconstrained submodular maximization, regularization, double greedy, non-oblivious local search, inapproximability
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

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