Incremental Maximization via Continuization

Yann Disser*, Max Klimm*, Kevin Schewior*, David Weckbecker*


Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

18 Downloads (Pure)


We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but also describes how to gradually grow the solution as the cardinality bound increases. The goal is to find an incremental solution that guarantees a good competitive ratio against the optimum solution for all cardinalities simultaneously. The central challenge is to characterize maximization problems where this is possible, and to determine the best-possible competitive ratio that can be attained. A lower bound of 2.18 and an upper bound of φ + 1 ≈ 2.618 are known on the competitive ratio for monotone and accountable objectives [Bernstein et al., Math. Prog., 2022], which capture a wide range of maximization problems. We introduce a continuization technique and identify an optimal incremental algorithm that provides strong evidence that φ+1 is the best-possible competitive ratio. Using this continuization, we obtain an improved lower bound of 2.246 by studying a particular recurrence relation whose characteristic polynomial has complex roots exactly beyond the lower bound. Based on the optimal continuous algorithm combined with a scaling approach, we also provide a 1.772-competitive randomized algorithm. We complement this by a randomized lower bound of 1.447 via Yao’s principle.

Titel50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
RedaktørerKousha Etessami, Uriel Feige, Gabriele Puppis
Antal sider17
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdatojul. 2023
ISBN (Elektronisk)9783959772785
StatusUdgivet - jul. 2023
Begivenhed50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Tyskland
Varighed: 10. jul. 202314. jul. 2023


Konference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
SponsorDeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron
NavnLeibniz International Proceedings in Informatics, LIPIcs

Bibliografisk note

Funding Information:
Funding Max Klimm: Supported by Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy, Berlin Mathematics Research Center (grant EXC-2046/1, Project 390685689). Kevin Schewior: Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B. David Weckbecker: Supported by DFG grant DI 2041/2.

Publisher Copyright:
© Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker.


Dyk ned i forskningsemnerne om 'Incremental Maximization via Continuization'. Sammen danner de et unikt fingeraftryk.