DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.23

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

Authors: Kobi Bodek and Moran Feldman

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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).

Cite as

Kobi Bodek and Moran Feldman. Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2022.23},
  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}
}

Search Results

Documents authored by Bodek, Kobi

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

Abstract

Cite as

Thanks for your feedback!

Could not send message