23 czerwca 2026 10:15
[Seminarium ZOK] Yann Disser: Incremental Maximization for a Broad Class of Objectives
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.
Joint work with David Weckbecker; published at ESA 2025.
Paper link: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.92