DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.92

Incremental Maximization for a Broad Class of Objectives

Authors: Yann Disser and David Weckbecker

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We consider incremental maximization problems, where the solution has to be built up gradually by adding elements one after the other. In every step, the incremental solution must be competitive, compared against the optimum solution of the current cardinality. We prove that a competitive solution always exists when the objective function is monotone and β-accountable, by providing a scaling algorithm that guarantees a constant competitive ratio. This generalizes known results and, importantly, yields the first competitive algorithm for the natural class of monotone and subadditive objective functions.

Cite as

Yann Disser and David Weckbecker. Incremental Maximization for a Broad Class of Objectives. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2025.92,
  author =	{Disser, Yann and Weckbecker, David},
  title =	{{Incremental Maximization for a Broad Class of Objectives}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{92:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.92},
  URN =		{urn:nbn:de:0030-drops-245613},
  doi =		{10.4230/LIPIcs.ESA.2025.92},
  annote =	{Keywords: incremental maximization, competitive analysis, subadditive functions}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.47

Incremental Maximization via Continuization

Authors: Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

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.

Cite as

Yann Disser, Max Klimm, Kevin Schewior, and David Weckbecker. Incremental Maximization via Continuization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ICALP.2023.47,
  author =	{Disser, Yann and Klimm, Max and Schewior, Kevin and Weckbecker, David},
  title =	{{Incremental Maximization via Continuization}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.47},
  URN =		{urn:nbn:de:0030-drops-180992},
  doi =		{10.4230/LIPIcs.ICALP.2023.47},
  annote =	{Keywords: incremental optimization, competitive analysis, robust matching, submodular function}
}

Search Results

Documents authored by Weckbecker, David

Incremental Maximization for a Broad Class of Objectives

Abstract

Cite as

Incremental Maximization via Continuization

Abstract

Cite as

Thanks for your feedback!

Could not send message