An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model

DOI10.1145/3313276.3316304zbMath1433.68590arXiv1811.03093OpenAlexW2963268806MaRDI QIDQ5212748

Aviad Rubinstein, Yaron Singer, Eric Balkanski

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.03093

zbMATH Keywords

adaptivityparallel algorithmsmatroidssubmodular optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (5)

Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Unnamed Item ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint

This page was built for publication: An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model