Speaker
Description
Yann Disser, Max Klimm, Kevin Schewior and David Weckbecker
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 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 $\varphi + 1 \approx 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 $\varphi + 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.