License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.29
URN: urn:nbn:de:0030-drops-84134
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8413/
Go to the corresponding LIPIcs Volume Portal

Garg, Apoorv ; Ranade, Abhiram G.

Train Scheduling on a Unidirectional Path

pdf-format:
LIPIcs-FSTTCS-2017-29.pdf (0.6 MB)

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
Collection: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Issue Date: 2018
Date of publication: 12.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI