Subquadratic Submodular Maximization with a General Matroid Constraint
<|reference_start|>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 - \epsilon)$-approximation algorithm that requires $\tilde{O}_{\epsilon}(\sqrt{r} n)$ independence oracle and value oracle queries, where $n$ is the number of elements in the matroid and $r \leq 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 $\tilde{O}_{\epsilon}(r^2 + \sqrt{r}n)$ 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 $\tilde{O}(r^{3/2} t)$ independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondr\'{a}k-Zenklusen [FOCS 2010] requires $O(r^2 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\'{a}k-Zenklusen focused on directed cycles of length two.<|reference_end|>
@article{kobayashi2024subquadratic,
    title={Subquadratic Submodular Maximization with a General Matroid Constraint},
    author={Yusuke Kobayashi, Tatsuya Terao},
    journal={arXiv preprint arXiv:2405.00359},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.00359},
    primaryClass={cs.DS}
}