1 Search Results for "Garg, Apoorv"


Document
Train Scheduling on a Unidirectional Path

Authors: Apoorv Garg and Abhiram G. Ranade

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)


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.

Cite as

Apoorv Garg and Abhiram G. Ranade. Train Scheduling on a Unidirectional Path. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.FSTTCS.2017.29,
  author =	{Garg, Apoorv and Ranade, Abhiram G.},
  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 =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.29},
  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}
}
  • Refine by Author
  • 1 Garg, Apoorv
  • 1 Ranade, Abhiram G.

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Combinatorial optimization
  • 1 Complexity analysis
  • 1 Max-delay minimization
  • 1 Train scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail