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.2018.99
URN: urn:nbn:de:0030-drops-91033
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9103/
Go to the corresponding LIPIcs Volume Portal

Soma, Tasuku ; Yoshida, Yuichi

A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

pdf-format:
LIPIcs-ICALP-2018-99.pdf (0.5 MB)

Abstract

In monotone submodular function maximization, approximation guarantees based on the curvature of the objective function have been extensively studied in the literature. However, the notion of curvature is often pessimistic, and we rarely obtain improved approximation guarantees, even for very simple objective functions.
In this paper, we provide a novel approximation guarantee by extracting an M^{natural}-concave function h:2^E -> R_+, a notion in discrete convex analysis, from the objective function f:2^E -> R_+. We introduce a novel notion called the M^{natural}-concave curvature of a given set function f, which measures how much f deviates from an M^{natural}-concave function, and show that we can obtain a (1-gamma/e-epsilon)-approximation to the problem of maximizing f under a cardinality constraint in polynomial time, where gamma is the value of the M^{natural}-concave curvature and epsilon > 0 is an arbitrary constant. Then, we show that we can obtain nontrivial approximation guarantees for various problems by applying the proposed algorithm.

BibTeX - Entry

@InProceedings{soma_et_al:LIPIcs:2018:9103,
  author =	{Tasuku Soma and Yuichi Yoshida},
  title =	{{A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{99:1--99:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9103},
  URN =		{urn:nbn:de:0030-drops-91033},
  doi =		{10.4230/LIPIcs.ICALP.2018.99},
  annote =	{Keywords: Submodular Function, Approximation Algorithm, Discrete Convex Analysis}
}

Keywords: Submodular Function, Approximation Algorithm, Discrete Convex Analysis
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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