2026-07-23T04:16:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18099 2024-03-06T11:01:00Z ddc:004 open_access

Incremental Maximization via Continuization Disser, Yann Klimm, Max Schewior, Kevin Weckbecker, David incremental optimization competitive analysis robust matching submodular function 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yann Disser and Max Klimm and Kevin Schewior and David Weckbecker 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.47 urn:nbn:de:0030-drops-180992 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.47 eng https://creativecommons.org/licenses/by/4.0/legalcode