TY - GEN
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 - Funding Information:
This work is supported by the German Research Foundation (DFG) under project ME 3825/1 and within project A07 of CRC TRR 154. It is partially funded in the framework of Matheon supported by the Einstein Foundation Berlin and by the Alexander von Humboldt Foundation. A version with proofs and illustrations is available on arXiv.
Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
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 arbi-trary 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 effciently 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 arbi-trary 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 effciently 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=85018402986&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-57586-5_3
DO - 10.1007/978-3-319-57586-5_3
M3 - Conference contribution
AN - SCOPUS:85018402986
SN - 9783319575858
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 19
EP - 30
BT - Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings
A2 - Fotakis, Dimitris
A2 - Pagourtzis, Aris
A2 - Paschos, Vangelis Th.
PB - Springer-Verlag
Y2 - 24 May 2017 through 26 May 2017
ER -