General Bounds for Incremental Maximization
- We propose a theoretical framework to capture incremental s
olutions to cardinality con-
strained maximization problems. The defining characterist
ic of our framework is that the
cardinality/support of the solution is bounded by a value
k
∈
N
that grows over time, and
we allow the solution to be extended one element at a time. We i
nvestigate the best-possible
competitive ratio of such an incremental solution, i.e., th
e 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 cardin
ality constrained maximization
problems like maximum matching, knapsack, and packing/cov
ering problems. We provide a
general 2
.
618-competitive incremental algorithm for this class of pr
oblems, 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 inc
remental greedy algorithm
that increases the objective value as much as possible in eac
h 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 submod-
ularity condition for the objective function, capturing pr
oblems like maximum (weighted)
(
b
-)matching and a variant of the maximum flow problem. We show t
hat the greedy algo-
rithm 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 transla
te to approximation ratios
for the underlying cardinality constrained problems.
MetadatenAuthor: | Aaron Bernstein, Yann Disser, Martin Groß |
---|
Document Type: | Article |
---|
Language: | English |
---|
Date of Publication (online): | 2017/06/30 |
---|
Date of first Publication: | 2017/08/07 |
---|
Release Date: | 2017/08/07 |
---|
Subprojects: | A07 |
---|