DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2012.97

Optimal Algorithms for Train Shunting and Relaxed List Update Problems

Authors: Tim Nonner and Alexander Souza

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

Abstract

This paper considers a Train Shunting problem which occurs in cargo train organizations: We have a locomotive travelling along a track segment and a collection of n cars, where each car has a source and a target. Whenever the train passes the source of a car, it needs to be added to the train, and on the target, the respective car needs to be removed. Any such operation at the end of the train incurs low shunting cost, but adding or removing truly in the interior requires a more complex shunting operation and thus yields high cost. The objective is to schedule the adding and removal of cars as to minimize the total cost. This problem can also be seen as a relaxed version of the well-known List Update problem, which may be of independent interest. We derive polynomial time algorithms for Train Shunting by reducing this problem to finding independent sets in bipartite graphs. This allows us to treat several variants of the problem in a generic way. Specifically, we obtain an algorithm with running time O(n^{5/2}) for the uniform case, where all low costs and all high costs are identical, respectively. Furthermore, for the non-uniform case we have running time of O(n^3). Both versions translate to a symmetric variant, where it is also allowed to add and remove cars at the front of the train at low cost. In addition, we formulate a dynamic program with running time O(n^4), which exploits the special structure of the graph. Although the running time is worse, it allows us to solve many extensions, e.g., prize-collection, economies of scale, and dependencies between consecutive stations.

Cite as

Tim Nonner and Alexander Souza. Optimal Algorithms for Train Shunting and Relaxed List Update Problems. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 97-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2012.97,
  author =	{Nonner, Tim and Souza, Alexander},
  title =	{{Optimal Algorithms for Train Shunting and Relaxed List Update Problems}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{97--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.97},
  URN =		{urn:nbn:de:0030-drops-37066},
  doi =		{10.4230/OASIcs.ATMOS.2012.97},
  annote =	{Keywords: Train shunting, optimal algorithm, independent set, dynamic programming}
}

Document

DOI: 10.4230/LIPIcs.STACS.2011.531

Balanced Interval Coloring

Authors: Antonios Antoniadis, Falk Hueffner, Pascal Lenzner, Carsten Moldenhauer, and Alexander Souza

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract

We consider the discrepancy problem of coloring n intervals with k colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time O(n log n + kn log k) for its construction. This is in particular interesting because many known results for discrepancy problems are non-constructive. This problem naturally models a load balancing scenario, where $n$~tasks with given start- and endtimes have to be distributed among $k$~servers. Our results imply that this can be done ideally balanced. When generalizing to $d$-dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any d >= 2 and any k >= 2 it is NP-complete to decide if such a solution exists, which implies also NP-hardness of the respective minimization problem. In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.

Cite as

Antonios Antoniadis, Falk Hueffner, Pascal Lenzner, Carsten Moldenhauer, and Alexander Souza. Balanced Interval Coloring. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 531-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2011.531,
  author =	{Antoniadis, Antonios and Hueffner, Falk and Lenzner, Pascal and Moldenhauer, Carsten and Souza, Alexander},
  title =	{{Balanced Interval Coloring}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{531--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.531},
  URN =		{urn:nbn:de:0030-drops-30413},
  doi =		{10.4230/LIPIcs.STACS.2011.531},
  annote =	{Keywords: Load balancing, discrepancy theory, NP-hardness}
}

Search Results

Documents authored by Souza, Alexander

Optimal Algorithms for Train Shunting and Relaxed List Update Problems

Abstract

Cite as

Balanced Interval Coloring

Abstract

Cite as

Thanks for your feedback!

Could not send message