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.APPROX/RANDOM.2021.14
URN: urn:nbn:de:0030-drops-147072
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14707/
Go to the corresponding LIPIcs Volume Portal

Huang, Chien-Chung ; Sellier, François

Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint

pdf-format:
LIPIcs-APPROX14.pdf (0.7 MB)

Abstract

We consider the problem of maximizing a submodular function under the b-matching constraint, in the semi-streaming model. Our main results can be summarized as follows.
- When the function is linear, i.e. for the maximum weight b-matching problem, we obtain a 2+ε approximation. This improves the previous best bound of 3+ε [Roie Levin and David Wajc, 2021].
- When the function is a non-negative monotone submodular function, we obtain a 3 + 2 √2 ≈ 5.828 approximation. This matches the currently best ratio [Roie Levin and David Wajc, 2021].
- When the function is a non-negative non-monotone submodular function, we obtain a 4 + 2 √3 ≈ 7.464 approximation. This ratio is also achieved in [Roie Levin and David Wajc, 2021], but only under the simple matching constraint, while we can deal with the more general b-matching constraint.
We also consider a generalized problem, where a k-uniform hypergraph is given with an extra matroid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. We extend our technique to this case to obtain an algorithm with an approximation of 8/3k+O(1).
Our algorithms build on the ideas of the recent works of Levin and Wajc [Roie Levin and David Wajc, 2021] and of Garg, Jordan, and Svensson [Paritosh Garg et al., 2021]. Our main technical innovation is to introduce a data structure and associate it with each vertex and the matroid, to record the extra information of the stored edges. After the streaming phase, these data structures guide the greedy algorithm to make better choices.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2021.14,
  author =	{Huang, Chien-Chung and Sellier, Fran\c{c}ois},
  title =	{{Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14707},
  URN =		{urn:nbn:de:0030-drops-147072},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.14},
  annote =	{Keywords: Maximum Weight Matching, Submodular Function Maximization, Streaming, Matroid}
}

Keywords: Maximum Weight Matching, Submodular Function Maximization, Streaming, Matroid
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

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