@inproceedings{d859e54c25624e7c89a58f759e4017cb,

title = "Parallelizing greedy for submodular set function maximization in matroids and beyond",

abstract = "We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized (1/2 − ϵ)-approximation in O log2(n)/ϵ2 rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondr{\'a}k to obtain a fractional solution that yields a near-optimal randomized (1 − 1/e − ϵ)-approximation in O log2(n)/ϵ3 rounds of adaptivity. For non-negative functions we obtain a 3 − 22 − ϵ - approximation and a fractional solution that yields a (1/e − ϵ)-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.",

keywords = "Matroids, Parallel algorithms, Submodular maximization",

author = "Chandra Chekuri and Kent Quanrud",

note = "Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

year = "2019",

month = jun,

day = "23",

doi = "10.1145/3313276.3316406",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "78--89",

editor = "Moses Charikar and Edith Cohen",

booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

}