4 Search Results for "Nonner, Tim"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.31
Improved and Parameterized Algorithms for Online Multi-Level Aggregation

Authors: Young-San Lin and Alex Turoczy

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski, Böhm, Byrka, Chrobak, Dürr, Folwarczný, Jeż, Sgall, Thang, and Veselý (ESA 2016, OR 2020). In this problem, requests arrive over time at the vertices of a given vertex-weighted tree, and each request has a deadline that it must be served by. The cost of serving a request equals the cost of a path from the root to the vertex where the request resides. Instead of serving each request individually, requests can be aggregated and served by transmitting a subtree from the root that spans the vertices on which the requests reside, to potentially be more cost-effective. The aggregated cost is the weight of the transmission subtree. The goal of MLAP-D is to find an aggregation solution that minimizes the total cost while serving all requests. MLAP-D generalizes some well-studied problems including the TCP acknowledgment problem and the joint replenishment problem, and arises in natural scenarios such as multi-casting, sensor networks, and supply chain management. We present improved and parameterized algorithms for MLAP-D. Our result is twofold. First, we present an e(D+1)-competitive algorithm where D is the depth of the tree. Second, we present an e(4H+2)-competitive algorithm where H is the caterpillar dimension of the tree. Here, H ≤ D and H ≤ log₂ |V| where |V| is the number of vertices in the given tree. The caterpillar dimension remains constant for rich but simple classes of trees, such as line graphs (H = 1), caterpillar graphs (H = 2), and lobster graphs (H = 3). To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. The state-of-the-art online algorithms are 6(D+1)-competitive by Buchbinder, Feldman, Naor, and Talmon (SODA 2017) and O(log |V|)-competitive by Azar and Touitou (FOCS 2020). Our framework outperforms the state-of-the-art ratios when H = o(min{D,log₂ |V|}). Our memory-based algorithms extend transmission subtrees with a cost comparable to transmission subtrees used to serve previous requests. Our simple framework directly applies to trees with any structure and differs from the previous frameworks that reduce the problem to trees with specific structures.
Cite as

Young-San Lin and Alex Turoczy. Improved and Parameterized Algorithms for Online Multi-Level Aggregation. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.SWAT.2026.31,
  author =	{Lin, Young-San and Turoczy, Alex},
  title =	{{Improved and Parameterized Algorithms for Online Multi-Level Aggregation}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.31},
  URN =		{urn:nbn:de:0030-drops-260673},
  doi =		{10.4230/LIPIcs.SWAT.2026.31},
  annote =	{Keywords: Online Algorithms, Approximation Algorithms, Graph Problems}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.15
Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments

Authors: Tim Nonner and Marco Laumanns

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
The Shortest Path with Alternatives (SPA) policy differs from classical shortest path routing in the following way: instead of providing an exact list of means of transportation to follow, this policy gives such a list for each stop, and the traveler is supposed to pick the first option from this list when waiting at some stop. First, we show that an optimal policy of this type can be computed in polynomial time for uniform arrival times under reasonable assumptions. A similar result was so far only known for Poisson arrival times, which are less realistic for frequency-based public transportation systems. Second, we experimentally evaluate such policies. In this context, our main finding is that SPA policies are surprisingly competitive compared to traditional shortest paths, and moreover yield a significant reduction of waiting times, and therefore improvement of user experience, compared to similar greedy approaches. Specifically, for roughly 25% of considered cases, we could decrease the expected waiting time by at least 20%. To run our experiments, we also describe a tool-chain to derive the necessary information from the popular GTFS-format, therefore allowing the application of SPA policies to a wide range of public transportation systems.
Cite as

Tim Nonner and Marco Laumanns. Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 15-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2014.15,
  author =	{Nonner, Tim and Laumanns, Marco},
  title =	{{Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.15},
  URN =		{urn:nbn:de:0030-drops-47494},
  doi =		{10.4230/OASIcs.ATMOS.2014.15},
  annote =	{Keywords: Shortest Path, Stochastic Optimization, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.34
Online Train Shunting

Authors: Vianney Boeuf and Frédéric Meunier

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2-competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
Cite as

Vianney Boeuf and Frédéric Meunier. Online Train Shunting. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 34-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boeuf_et_al:OASIcs.ATMOS.2014.34,
  author =	{Boeuf, Vianney and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Online Train Shunting}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{34--45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.34},
  URN =		{urn:nbn:de:0030-drops-47512},
  doi =		{10.4230/OASIcs.ATMOS.2014.34},
  annote =	{Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
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}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2014
  • 1 2012

  • Refine by Author
  • 2 Nonner, Tim
  • 1 Boeuf, Vianney
  • 1 Laumanns, Marco
  • 1 Lin, Young-San
  • 1 Meunier, Frédéric
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 3 OASIcs

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Bipartite graph
  • 1 Graph Problems
  • 1 Online Algorithms
  • 1 Public Transportation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact