Abed, F. ; Chen, L. ; Disser, Y. ; Groß, M. ; Megow, N. ; Meißner, J. ; Richter, A. ; Rischke, R. (2017)
Scheduling Maintenance Jobs in Networks.
10th International Conference on Algorithms and Complexity. Athens, Greece (24.-26.05.2017)
doi: 10.1007/978-3-319-57586-5_3
Conference or Workshop Item, Bibliographie
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 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.
| Item Type: | Conference or Workshop Item |
|---|---|
| Erschienen: | 2017 |
| Creators: | Abed, F. ; Chen, L. ; Disser, Y. ; Groß, M. ; Megow, N. ; Meißner, J. ; Richter, A. ; Rischke, R. |
| Type of entry: | Bibliographie |
| Title: | Scheduling Maintenance Jobs in Networks |
| Language: | English |
| Date: | 12 April 2017 |
| Publisher: | Springer |
| Book Title: | CIAC 2017: Algorithms and Complexity |
| Series: | Lecture Notes in Computer Science |
| Series Volume: | 10236 |
| Event Title: | 10th International Conference on Algorithms and Complexity |
| Event Location: | Athens, Greece |
| Event Dates: | 24.-26.05.2017 |
| DOI: | 10.1007/978-3-319-57586-5_3 |
| Corresponding Links: | |
| 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 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. |
| Divisions: | Exzellenzinitiative Exzellenzinitiative > Graduate Schools Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE) 04 Department of Mathematics 04 Department of Mathematics > Optimization 04 Department of Mathematics > Optimization > Discrete Optimization |
| Date Deposited: | 07 Mar 2017 07:04 |
| Last Modified: | 18 Aug 2022 11:58 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum