Title: General Bounds for Incremental Maximization,
Abstract: We propose a theoretical framework to capture incremental solutions to
cardinality constrained maximization problems. The defining characteristic of
our framework is that the cardinality/support of the solution is bounded by a
value $k\in\mathbb{N}$ that grows over time, and we allow the solution to be
extended one element at a time. We investigate the best-possible competitive
ratio of such an incremental solution, i.e., the worst ratio over all $k$
between the incremental solution after $k$ steps and an optimum solution of
cardinality $k$. We define a large class of problems that contains many
important cardinality constrained maximization problems like maximum matching,
knapsack, and packing/covering problems. We provide a general
$2.618$-competitive incremental algorithm for this class of problems, and show
that no algorithm can have competitive ratio below $2.18$ in general.
In the second part of the paper, we focus on the inherently incremental
greedy algorithm that increases the objective value as much as possible in each
step. This algorithm is known to be $1.58$-competitive for submodular objective
functions, but it has unbounded competitive ratio for the class of incremental
problems mentioned above. We define a relaxed submodularity condition for the
objective function, capturing problems like maximum (weighted) ($b$-)matching
and a variant of the maximum flow problem. We show that the greedy algorithm
has competitive ratio (exactly) $2.313$ for the class of problems that satisfy
this relaxed submodularity condition.
Note that our upper bounds on the competitive ratios translate to
approximation ratios for the underlying cardinality constrained problems.