Submodular Maximization in Exactly $n$ Queries
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910580283015168 |
|---|---|
| author | Balkanski, Eric DiSilvio, Steven Kuhnle, Alan Peng, ChunLi |
| author_facet | Balkanski, Eric DiSilvio, Steven Kuhnle, Alan Peng, ChunLi |
| contents | In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying the submodular function, for both the case when the submodular function is monotone and the general submodular case. In particular, we present a 1/4 approximation algorithm for the monotone case that uses exactly one query per element, which gives the same total number of queries n as the number of queries required to compute the maximum singleton. For the general case, we present a constant factor approximation algorithm that requires 2 queries per element, which is the first algorithm for this problem with linear query complexity in the size of the ground set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00148 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Submodular Maximization in Exactly $n$ Queries Balkanski, Eric DiSilvio, Steven Kuhnle, Alan Peng, ChunLi Data Structures and Algorithms In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying the submodular function, for both the case when the submodular function is monotone and the general submodular case. In particular, we present a 1/4 approximation algorithm for the monotone case that uses exactly one query per element, which gives the same total number of queries n as the number of queries required to compute the maximum singleton. For the general case, we present a constant factor approximation algorithm that requires 2 queries per element, which is the first algorithm for this problem with linear query complexity in the size of the ground set. |
| title | Submodular Maximization in Exactly $n$ Queries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.00148 |