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.2019.54
URN: urn:nbn:de:0030-drops-106303
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10630/
Go to the corresponding LIPIcs Volume Portal

Ene, Alina ; Nguyen, Huy L.

Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint

pdf-format:
LIPIcs-ICALP-2019-54.pdf (0.5 MB)

Abstract

We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations.

BibTeX - Entry

@InProceedings{ene_et_al:LIPIcs:2019:10630,
  author =	{Alina Ene and Huy L. Nguyen},
  title =	{{Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10630},
  URN =		{urn:nbn:de:0030-drops-106303},
  doi =		{10.4230/LIPIcs.ICALP.2019.54},
  annote =	{Keywords: submodular maximization, matroid constraints, fast running times}
}

Keywords: submodular maximization, matroid constraints, fast running times
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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