2026-07-24T05:03:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24561 2025-12-16T14:00:50Z ddc:004 open_access

Incremental Maximization for a Broad Class of Objectives Disser, Yann Weckbecker, David incremental maximization competitive analysis subadditive functions 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yann Disser and David Weckbecker 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.92 urn:nbn:de:0030-drops-245613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.92 eng https://creativecommons.org/licenses/by/4.0/legalcode