The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, Silvio Lattanzi *, Ashkan Norouzi-Fard *, Ola Svensson, Morteza Zadimoghaddam * · 2024
Read The Cost of Consistency: Submodular Maximization with Constant Recourse by Paul Dütting, Federico Fusco, Silvio Lattanzi *, Ashkan Norouzi-Fard *, Ola Svensson, Morteza Zadimoghaddam * (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-02492.txt.
Description
Choosing the best bundle under a rule of diminishing returns is a staple computing problem. Doing it online, as options arrive, raises a tension: churning the answer chases quality but breaks consistency. Paul Dütting and co-authors ask how good an online chooser can be. The catch: it may change its answer only a constant number of times per step. They prove sharp limits on the achievable quality.
For general monotone problems the ceiling is two thirds of optimal, and for coverage problems it rises to three quarters; both bounds are tight. Their best algorithms behind those bounds are too slow for practice, so they add a fast randomised method reaching just over half of optimal. Earlier hardness results for deterministic methods complete a clean separation between coin-flipping and fixed-rule choosers.
Catalog record
| CREATOR | Paul Dütting, Federico Fusco, Silvio Lattanzi *, Ashkan Norouzi-Fard *, Ola Svensson, Morteza Zadimoghaddam * |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-02492