The Cost of Consistency: Submodular Maximization with Constant Recourse
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912142414839808 |
|---|---|
| author | Dütting, Paul Fusco, Federico Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola Zadimoghaddam, Morteza |
| author_facet | Dütting, Paul Fusco, Federico Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola Zadimoghaddam, Morteza |
| contents | In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowed to make at most a constant number of updates per step. We show a tight information-theoretic bound of $\tfrac{2}{3}$ for general monotone submodular functions, and an improved (also tight) bound of $\tfrac{3}{4}$ for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a $0.51$-approximation. Combined with an information-theoretic hardness of $\tfrac{1}{2}$ for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02492 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Cost of Consistency: Submodular Maximization with Constant Recourse Dütting, Paul Fusco, Federico Lattanzi, Silvio Norouzi-Fard, Ashkan Svensson, Ola Zadimoghaddam, Morteza Data Structures and Algorithms Machine Learning In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowed to make at most a constant number of updates per step. We show a tight information-theoretic bound of $\tfrac{2}{3}$ for general monotone submodular functions, and an improved (also tight) bound of $\tfrac{3}{4}$ for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a $0.51$-approximation. Combined with an information-theoretic hardness of $\tfrac{1}{2}$ for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms. |
| title | The Cost of Consistency: Submodular Maximization with Constant Recourse |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2412.02492 |