Subquadratic Submodular Maximization with a General Matroid Constraint
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911861177319424 |
|---|---|
| author | Kobayashi, Yusuke Terao, Tatsuya |
| author_facet | Kobayashi, Yusuke Terao, Tatsuya |
| contents | We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized $(1 - 1/e - ε)$-approximation algorithm that requires $\tilde{O}_ε(\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}_ε(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á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ák-Zenklusen focused on directed cycles of length two. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00359 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subquadratic Submodular Maximization with a General Matroid Constraint Kobayashi, Yusuke Terao, Tatsuya Data Structures and Algorithms We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized $(1 - 1/e - ε)$-approximation algorithm that requires $\tilde{O}_ε(\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}_ε(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á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ák-Zenklusen focused on directed cycles of length two. |
| title | Subquadratic Submodular Maximization with a General Matroid Constraint |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.00359 |