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

CREATORPaul Dütting, Federico Fusco, Silvio Lattanzi *, Ashkan Norouzi-Fard *, Ola Svensson, Morteza Zadimoghaddam *
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-02492

Browse the full library · About the Tower of Babel