Incremental Maximization via Continuization

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

17 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.

Original languageEnglish
Title of host publication50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
EditorsKousha Etessami, Uriel Feige, Gabriele Puppis
Number of pages17
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication dateJul 2023
Article number47
ISBN (Electronic)9783959772785
DOIs
Publication statusPublished - Jul 2023
Event50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany
Duration: 10. Jul 202314. Jul 2023

Conference

Conference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Country/TerritoryGermany
CityPaderborn
Period10/07/202314/07/2023
SponsorDeepL, et al., Paderborn Center for Parallel Computing (PC2), REPLY, SFB 901, Stiebel Eltron
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume261
ISSN1868-8969

Bibliographical note

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

Keywords

  • competitive analysis
  • incremental optimization
  • robust matching
  • submodular function

Fingerprint

Dive into the research topics of 'Incremental Maximization via Continuization'. Together they form a unique fingerprint.

Cite this