Subquadratic Submodular Maximization with a General Matroid Constraint

We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized (1 - 1/e -) -approximation algorithm that requires O_ (r n) independence oracle and value oracle queries, where n is the number of elements in the matroid and r n is the rank of the matroid. This improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz Mathematics of Operations Research 2017 that requires O_ (r² + rn) queries. Our algorithm is based on continuous relaxation, as with other submodular maximization algorithms in the literature. To achieve subquadratic query complexity, we develop a new rounding algorithm, which is our main technical contribution. The rounding algorithm takes as input a point represented as a convex combination of t bases of a matroid and rounds it to an integral solution. Our rounding algorithm requires O (r^3/2 t) independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondr\'ak-Zenklusen FOCS 2010 requires O (r² t) independence oracle queries. A key idea in our rounding algorithm is to use a directed cycle of arbitrary length in an auxiliary graph, while the algorithm of Chekuri-Vondr\'ak-Zenklusen focused on directed cycles of length two.