We consider the problem of maximizing a fractionally subadditive function under a knapsack constraint that grows over time. An incremental solution to this problem is given by an order in which to include the elements of the ground set, and the competitive ratio of an incremental solution is defined by the worst ratio over all capacities relative to an optimum solution of the corresponding capacity. We present an algorithm that finds an incremental solution of competitive ratio at most $\max\{3.293\sqrt{M},2M\}$, under the assumption that the values of singleton sets are in the range $[1,M]$, and we give a lower bound of $\max\{2.449,M\}$ on the attainable competitive ratio. In addition, we establish that our framework captures potential-based flows between two vertices, and we give a tight bound of 2 for the incremental maximization of classical flows with unit capacities.
We investigate the problem of scheduling the maintenance
of edges in a network, motivated by the goal of minimizing outages in
transportation or telecommunication networks. We focus on maintaining
connectivity between two nodes over time; for the special case of path
networks, this is related to the problem of minimizing the busy time of
machines.
We show that the problem can be solved in polynomial time in arbitrary
networks if preemption is allowed. If preemption is restricted to integral
time points, the problem is NP-hard and in the non-preemptive case
we give strong non-approximability results. Furthermore, we give tight
bounds on the power of preemption, that is, the maximum ratio of the
values of non-preemptive and preemptive optimal solutions.
Interestingly, the preemptive and the non-preemptive problem can be
solved efficiently on paths, whereas we show that mixing both leads to a
weakly NP-hard problem that allows for a simple 2-approximation.
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.