- 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.