Incremental Maximization via Continuization

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

*Kontaktforfatter

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

18 Downloads (Pure)

Abstract

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.

OriginalsprogEngelsk
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
Artikelnummer47
ISBN (Elektronisk)9783959772785
DOI
StatusUdgivet - jul. 2023
Begivenhed50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Tyskland
Varighed: 10. jul. 202314. jul. 2023

Konference

Konference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Land/OmrådeTyskland
ByPaderborn
Periode10/07/202314/07/2023
SponsorDeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind261
ISSN1868-8969

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.

Fingeraftryk

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

Citationsformater