Scheduling maintenance jobs in networks

Fidaa Abed, Lin Chen, Yann Disser, Martin Groß, Nicole Megow, Julie Meißner, Alexander T. Richter, Roman Rischke

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings
EditorsDimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos
PublisherSpringer-Verlag
Pages19-30
Number of pages12
ISBN (Print)9783319575858
DOIs
StatePublished - 2017
Event10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece
Duration: May 24 2017May 26 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10236 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Algorithms and Complexity, CIAC 2017
CountryGreece
CityAthens
Period05/24/1705/26/17

Keywords

  • Approximation algorithm
  • Complexity theory
  • Connectivity
  • Maintenance
  • Scheduling

Fingerprint Dive into the research topics of 'Scheduling maintenance jobs in networks'. Together they form a unique fingerprint.

Cite this