TY - JOUR
T1 - Scheduling maintenance jobs in networks
AU - Abed, Fidaa
AU - Chen, Lin
AU - Disser, Yann
AU - Groß, Martin
AU - Megow, Nicole
AU - Meißner, Julie
AU - Richter, Alexander T.
AU - Rischke, Roman
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2019/1/6
Y1 - 2019/1/6
N2 - 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.
AB - 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.
KW - Approximation algorithm
KW - Complexity theory
KW - Connectivity
KW - Maintenance
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=85042681416&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2018.02.020
DO - 10.1016/j.tcs.2018.02.020
M3 - Article
AN - SCOPUS:85042681416
VL - 754
SP - 107
EP - 121
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -