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.ISAAC.2020.64
URN: urn:nbn:de:0030-drops-134082
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13408/
Go to the corresponding LIPIcs Volume Portal

Santiago, Richard ; Yoshida, Yuichi

Weakly Submodular Function Maximization Using Local Submodularity Ratio

pdf-format:
LIPIcs-ISAAC-2020-64.pdf (0.5 MB)

Abstract

Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.

BibTeX - Entry

@InProceedings{santiago_et_al:LIPIcs:2020:13408,
  author =	{Richard Santiago and Yuichi Yoshida},
  title =	{{Weakly Submodular Function Maximization Using Local Submodularity Ratio}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{64:1--64:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13408},
  URN =		{urn:nbn:de:0030-drops-134082},
  doi =		{10.4230/LIPIcs.ISAAC.2020.64},
  annote =	{Keywords: weakly submodular, non-monotone, local submodularity ratio}
}

Keywords: weakly submodular, non-monotone, local submodularity ratio
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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