Submodular maximization with matroid and packing constraints in parallel

DOI10.1145/3313276.3316389zbMath1433.68593arXiv1808.09987OpenAlexW2953374984MaRDI QIDQ5212750

No author found.

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/1808.09987

zbMATH Keywords

packingparallel complexitymatroidDR-submodular maximization

Mathematics Subject Classification ID

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

Related Items (5)

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ 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

This page was built for publication: Submodular maximization with matroid and packing constraints in parallel