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

Feldman, Moran ; Norouzi-Fard, Ashkan ; Svensson, Ola ; Zenklusen, Rico

Submodular Maximization Subject to Matroid Intersection on the Fly

pdf-format:
LIPIcs-ESA-2022-52.pdf (0.9 MB)

Abstract

Despite a surge of interest in submodular maximization in the data stream model, there remain significant gaps in our knowledge about what can be achieved in this setting, especially when dealing with multiple constraints. In this work, we nearly close several basic gaps in submodular maximization subject to k matroid constraints in the data stream model. We present a new hardness result showing that super polynomial memory in k is needed to obtain an o(k/(log k))-approximation. This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation by maintaining a set of elements whose size is independent of the stream size. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a 2-approximation may exist in this setting, and only a complexity-theoretic hardness of 1.91 was known. We prove an unconditional hardness of 2.69.

BibTeX - Entry

@InProceedings{feldman_et_al:LIPIcs.ESA.2022.52,
  author =	{Feldman, Moran and Norouzi-Fard, Ashkan and Svensson, Ola and Zenklusen, Rico},
  title =	{{Submodular Maximization Subject to Matroid Intersection on the Fly}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{52:1--52:14},
  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/16990},
  URN =		{urn:nbn:de:0030-drops-169902},
  doi =		{10.4230/LIPIcs.ESA.2022.52},
  annote =	{Keywords: Submodular Maximization, Matroid Intersection, Streaming Algorithms}
}

Keywords: Submodular Maximization, Matroid Intersection, Streaming Algorithms
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