Garg, Apoorv ;
Ranade, Abhiram G.
Train Scheduling on a Unidirectional Path
Abstract
We formulate what might be the simplest train scheduling problem considered in the literature and show it to be NP-hard. We also give a log-factor randomised algorithm for it. In our problem we have a unidirectional train track with equidistant stations, each station initially having at most one train. In addition, there can be at most one train poised to enter each station. The trains must move to their destinations subject to the constraint that at every time instant there can be at most one train at each station and on the track between stations. The goal is to minimise the maximum delay of any train. Our problem can also be interpreted as a packet routing problem, and our work strengthens the hardness results from that literature.
BibTeX - Entry
@InProceedings{garg_et_al:LIPIcs:2018:8413,
author = {Apoorv Garg and Abhiram G. Ranade},
title = {{Train Scheduling on a Unidirectional Path}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {29:1--29:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-055-2},
ISSN = {1868-8969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8413},
URN = {urn:nbn:de:0030-drops-84134},
doi = {10.4230/LIPIcs.FSTTCS.2017.29},
annote = {Keywords: Combinatorial optimization, Train scheduling, Max-delay minimization, Complexity analysis, Approximation algorithm}
}
|
Keywords: |
|
Combinatorial optimization, Train scheduling, Max-delay minimization, Complexity analysis, Approximation algorithm |
|
Seminar: |
|
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
|
|
Issue date: |
|
2018 |
|
Date of publication: |
|
2018 |
2018
