Parallelizing greedy for submodular set function maximization in matroids and beyond

DOI10.1145/3313276.3316406zbMath1433.68591arXiv1811.12568OpenAlexW2963059222MaRDI QIDQ5212749

Kent Quanrud, Chandra Chekuri

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.12568

zbMATH Keywords

parallel algorithmsmatroidssubmodular maximization

Mathematics Subject Classification ID

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

Related Items

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Two-stage stochastic max-weight independent set problems ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Unnamed Item ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Non-Submodular Maximization with Matroid and Knapsack Constraints