An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model

Eric Balkanski (), Aviad Rubinstein () and Yaron Singer ()
Additional contact information
Eric Balkanski: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Aviad Rubinstein: Department of Computer Science, Stanford University, Stanford, California 94305
Yaron Singer: School of Engineering and Applied Sciences, Harvard University, Cambridge, Massachusetts 02138

Operations Research, 2022, vol. 70, issue 5, 2967-2981

Abstract: In this paper, we study submodular maximization under a matroid constraint in the adaptive complexity model. This model was recently introduced in the context of submodular optimization to quantify the information theoretic complexity of black-box optimization in a parallel computation model. Despite the burst in work on submodular maximization in the adaptive complexity model, the fundamental problem of maximizing a monotone submodular function under a matroid constraint has remained elusive. In particular, all known techniques fail for this problem and there are no known constant factor approximation algorithms whose adaptivity is sublinear in the rank of the matroid k or in the worst case sublinear in the size of the ground set n . We present an algorithm that has an approximation guarantee arbitrarily close to the optimal 1 − 1 / e for monotone submodular maximization under a matroid constraint and has near-optimal adaptivity of O ( log ( n ) log ( k ) ) . This result is obtained using a novel technique of adaptive sequencing , which departs from previous techniques for submodular maximization in the adaptive complexity model. In addition to our main result, we show how to use this technique to design other approximation algorithms with strong approximation guarantees and polylogarithmic adaptivity.

Keywords: Optimization; submodular optimization; parallel algorithms; matroids; adaptivity (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2170 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:5:p:2967-2981

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().