Submodular Maximization Subject to Matroid Intersection on the Fly
OPEN ACCESS
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
30th Annual European Symposium on Algorithms (ESA 2022)
Volume
244
Pages / Article No.
52
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
30th Annual European Symposium on Algorithms (ESA 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Submodular Maximization; matroid intersection; Streaming Algorithms
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
184622 - Toward Stronger Approximation Algorithms for Fundamental Network Design and Optimization Problems (SNF)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)
817750 - Fundamental Problems at the Interface of Combinatorial Optimization with Integer Programming and Online Optimization (EC)