22 Search Results for "Mihal�k, Mat��"


Document
On Sorting with a Network of Two Stacks

Authors: Matúš Mihalák and Marc Pont

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)


Abstract
Sorting with stacks is a collection of problems that deal with sorting a sequence of numbers by pushing and popping the numbers to and from a given set of stacks. Multiple concrete decision or optimization questions are formed by restricting the access to the stacks. The motivation comes, e.g., from shunting train wagons in shunting yards, shunting trams in depots, or in stacking cargo containers on cargo ships or storage yards in transshipment terminals. We consider the problem of sorting a permutation of n integers 1,2,...,n using k >= 2 stacks. In this problem, elements from the input sequence are pushed one-by-one (in the order of the elements in the sequence) to one of the k stacks. At any time, an element from a stack can be popped and pushed to another stack; such an operation is called a shuffle. Also, at any time, an element can be popped from a stack and placed to the output sequence. We can only place the elements to the output in the increasing order of their value such that at the end the output is the ordered sequence of the elements. The problem asks to minimize the number of shuffles in the process. It is known that for k >= 4, the problem is NP-hard, and that there is no approximation algorithm unless P=NP. For k >= 3, it is known that at most O(n log n) shuffles are needed for any input sequence. For the case when k=2, there exist input sequences that require Omega(n^{2-epsilon}) shuffles, for any epsilon>0. Nothing substantially more is known for the case of k=2. In this paper, we study the following variant of the problem with k=2 stacks: no shuffle and no placement to the output sequence can happen before every element is in one of the two stacks. We show that our problem can be seen as the MinUnCut problem by providing a polynomial-time reduction, and thus we show that there exists a randomized O(sqrt{log n})-approximation algorithm and a deterministic O(log n)-approximation algorithm for our problem.

Cite as

Matúš Mihalák and Marc Pont. On Sorting with a Network of Two Stacks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{mihalak_et_al:OASIcs.ATMOS.2019.3,
  author =	{Mihal\'{a}k, Mat\'{u}\v{s} and Pont, Marc},
  title =	{{On Sorting with a Network of Two Stacks}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{3:1--3:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.3},
  URN =		{urn:nbn:de:0030-drops-114159},
  doi =		{10.4230/OASIcs.ATMOS.2019.3},
  annote =	{Keywords: Sorting, Stacks, Optimization, Algorithms, Reduction, MinUnCut}
}
Document
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Authors: Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.

Cite as

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45,
  author =	{Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.},
  title =	{{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45},
  URN =		{urn:nbn:de:0030-drops-99933},
  doi =		{10.4230/LIPIcs.ISAAC.2018.45},
  annote =	{Keywords: approximation algorithm, matching, clustering problem}
}
Document
Collective Fast Delivery by Energy-Efficient Agents

Authors: Andreas Bärtschi, Daniel Graf, and Matús Mihalák

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths). The agents have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0, with respect to the following: Each agent i has a weight omega_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity upsilon_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the item arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon * T + (1-epsilon)* E, for a given epsilon in (0,1). We show that (i) is solvable in polynomial time, and show that (ii) is polynomial-time solvable for uniform velocities and solvable in time O(n+k log k) for arbitrary velocities on paths, but in general is NP-hard even on planar graphs. As a corollary of our hardness result, (iii) is NP-hard, too. We show that there is a 2-approximation algorithm for (iii) using a single agent.

Cite as

Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective Fast Delivery by Energy-Efficient Agents. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.MFCS.2018.56,
  author =	{B\"{a}rtschi, Andreas and Graf, Daniel and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Collective Fast Delivery by Energy-Efficient Agents}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{56:1--56:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.56},
  URN =		{urn:nbn:de:0030-drops-96381},
  doi =		{10.4230/LIPIcs.MFCS.2018.56},
  annote =	{Keywords: delivery, mobile agents, time/energy optimization, complexity, algorithms}
}
Document
Robust Routing in Urban Public Transportation: Evaluating Strategies that Learn From the Past

Authors: Katerina Böhmová, Matúš Mihalák, Peggy Neubert, Tobias Pröger, and Peter Widmayer

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)


Abstract
Given an urban public transportation network and historic delay information, we consider the problem of computing reliable journeys. We propose new algorithms based on our recently presented solution concept (Böhmová et al., ATMOS 2013), and perform an experimental evaluation using real-world delay data from Zürich, Switzerland. We compare these methods to natural approaches as well as to our recently proposed method which can also be used to measure typicality of past observations. Moreover, we demonstrate how this measure relates to the predictive quality of the individual methods. In particular, if the past observations are typical, then the learning- based methods are able to produce solutions that perform well on typical days, even in the presence of large delays.

Cite as

Katerina Böhmová, Matúš Mihalák, Peggy Neubert, Tobias Pröger, and Peter Widmayer. Robust Routing in Urban Public Transportation: Evaluating Strategies that Learn From the Past. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 68-81, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bohmova_et_al:OASIcs.ATMOS.2015.68,
  author =	{B\"{o}hmov\'{a}, Katerina and Mihal\'{a}k, Mat\'{u}\v{s} and Neubert, Peggy and Pr\"{o}ger, Tobias and Widmayer, Peter},
  title =	{{Robust Routing in Urban Public Transportation: Evaluating Strategies that Learn From the Past}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{68--81},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.68},
  URN =		{urn:nbn:de:0030-drops-54542},
  doi =		{10.4230/OASIcs.ATMOS.2015.68},
  annote =	{Keywords: public transportation, route planning, robustness, optimization, experiments}
}
Document
Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks

Authors: Matúš Mihalák and Sandro Montanari

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)


Abstract
Based on time-dependent travel times for N past days, we consider the computation of robust routes according to the min-max relative regret criterion. For this method we seek a path minimizing its maximum weight in any one of the N days, normalized by the weight of an optimum for the respective day. In order to speed-up this computationally demanding approach, we observe that its output belongs to the Pareto front of the network with time-dependent multi-criteria edge weights. We adapt a well-known algorithm for computing Pareto fronts in time-dependent graphs and apply the bi-directional search technique to it. We also show how to parametrize this algorithm by a value K to compute a K-approximate Pareto front. An experimental evaluation for the cases N = 2 and N = 3 indicates a considerable speed-up of the bi-directional search over the uni-directional.

Cite as

Matúš Mihalák and Sandro Montanari. Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 82-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{mihalak_et_al:OASIcs.ATMOS.2015.82,
  author =	{Mihal\'{a}k, Mat\'{u}\v{s} and Montanari, Sandro},
  title =	{{Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{82--94},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.82},
  URN =		{urn:nbn:de:0030-drops-54561},
  doi =		{10.4230/OASIcs.ATMOS.2015.82},
  annote =	{Keywords: shortest path, time-dependent, bi-criteria, bi-directional search, min-max relative regret}
}
Document
Complete Volume
OASIcs, Volume 42, ATMOS'14, Complete Volume

Authors: Stefan Funke and Matúš Mihalák

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


Abstract
OASIcs, Volume 42, ATMOS'14, Complete Volume

Cite as

14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Proceedings{funke_et_al:OASIcs.ATMOS.2014,
  title =	{{OASIcs, Volume 42, ATMOS'14, Complete Volume}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014},
  URN =		{urn:nbn:de:0030-drops-47613},
  doi =		{10.4230/OASIcs.ATMOS.2014},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Combinatorics, Graph Theory, Applications}
}
Document
Front Matter
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Stefan Funke and Matús Mihalák

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


Abstract
Frontmatter, Table of Contents, Preface, Workshop Organization

Cite as

14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. i-ix, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{funke_et_al:OASIcs.ATMOS.2014.i,
  author =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--ix},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.i},
  URN =		{urn:nbn:de:0030-drops-47470},
  doi =		{10.4230/OASIcs.ATMOS.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time

Authors: Julian Dibbelt, Ben Strasser, and Dorothea Wagner

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


Abstract
We study the problem of computing delay-robust routes in timetable networks. Instead of a single path we compute a decision graph containing all stops and trains/vehicles that might be relevant. Delays are formalized using a stochastic model. We show how to compute a decision graph that minimizes the expected arrival time while bounding the latest arrival time over all sub-paths. Finally we show how the information contained within a decision graph can compactly be represented to the user. We experimentally evaluate our algorithms and show that the running times allow for interactive usage on a realistic train network.

Cite as

Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{dibbelt_et_al:OASIcs.ATMOS.2014.1,
  author =	{Dibbelt, Julian and Strasser, Ben and Wagner, Dorothea},
  title =	{{Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.1},
  URN =		{urn:nbn:de:0030-drops-47488},
  doi =		{10.4230/OASIcs.ATMOS.2014.1},
  annote =	{Keywords: Algorithms, Optimization, Delay-robustness, Route planning, Public transportation}
}
Document
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-dev.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
Locating Battery Charging Stations to Facilitate Almost Shortest Paths

Authors: Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal

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


Abstract
We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.

Cite as

Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal. Locating Battery Charging Stations to Facilitate Almost Shortest Paths. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 25-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{arkin_et_al:OASIcs.ATMOS.2014.25,
  author =	{Arkin, Esther M. and Carmi, Paz and Katz, Matthew J. and Mitchell, Joseph S. B. and Segal, Michael},
  title =	{{Locating Battery Charging Stations to Facilitate Almost Shortest Paths}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{25--33},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.25},
  URN =		{urn:nbn:de:0030-drops-47500},
  doi =		{10.4230/OASIcs.ATMOS.2014.25},
  annote =	{Keywords: approximation algorithms; geometric spanners; transportation networks}
}
Document
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-dev.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
Engineering Graph-Based Models for Dynamic Timetable Information Systems

Authors: Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis

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


Abstract
Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks. In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.

Cite as

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Engineering Graph-Based Models for Dynamic Timetable Information Systems. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 46-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{cionini_et_al:OASIcs.ATMOS.2014.46,
  author =	{Cionini, Alessio and D'Angelo, Gianlorenzo and D'Emidio, Mattia and Frigioni, Daniele and Giannakopoulou, Kalliopi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Engineering Graph-Based Models for Dynamic Timetable Information Systems}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{46--61},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.46},
  URN =		{urn:nbn:de:0030-drops-47522},
  doi =		{10.4230/OASIcs.ATMOS.2014.46},
  annote =	{Keywords: Timetabling, dynamic updates, queries, shortest paths}
}
Document
Local Search for the Resource Constrained Assignment Problem

Authors: Markus Reuther

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


Abstract
The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature.

Cite as

Markus Reuther. Local Search for the Resource Constrained Assignment Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 62-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{reuther:OASIcs.ATMOS.2014.62,
  author =	{Reuther, Markus},
  title =	{{Local Search for the Resource Constrained Assignment Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{62--78},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.62},
  URN =		{urn:nbn:de:0030-drops-47538},
  doi =		{10.4230/OASIcs.ATMOS.2014.62},
  annote =	{Keywords: Assignment Problem, Local Search, Rolling Stock Rotation Problem, Vehicle Routing Problem}
}
Document
A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem

Authors: Ralf Borndörfer, Markus Reuther, and Thomas Schlechte

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


Abstract
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.

Cite as

Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 79-91, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2014.79,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas},
  title =	{{A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation  Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{79--91},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.79},
  URN =		{urn:nbn:de:0030-drops-47549},
  doi =		{10.4230/OASIcs.ATMOS.2014.79},
  annote =	{Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem}
}
Document
Mathematical programming models for scheduling locks in sequence

Authors: Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma

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


Abstract
We investigate the scheduling of series of consecutive locks. This setting occurs naturally along canals and waterways. We describe a problem that generalizes different models that have been studied in literature. Our contribution is to (i) provide two distinct mathematical programming formulations, and compare them empirically, (ii) show how these models allow for minimizing emission by having the speed of a ship as a decision variable, (iii) to compare, on realistic instances, the optimum solution found by solving the models with the outcome of a decentralized heuristic.

Cite as

Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma. Mathematical programming models for scheduling locks in sequence. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 92-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{passchyn_et_al:OASIcs.ATMOS.2014.92,
  author =	{Passchyn, Ward and Briskorn, Dirk and Spieksma, Frits C.R.},
  title =	{{Mathematical programming models for scheduling locks in sequence}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{92--106},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.92},
  URN =		{urn:nbn:de:0030-drops-47553},
  doi =		{10.4230/OASIcs.ATMOS.2014.92},
  annote =	{Keywords: Mixed Integer Programming, Inland Waterways, Lock Scheduling}
}
  • Refine by Author
  • 6 Mihalák, Matús
  • 4 Mihalák, Matúš
  • 3 Widmayer, Peter
  • 2 Böhmová, Katerina
  • 2 Dibbelt, Julian
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Approximation algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 3 Algorithms
  • 3 Optimization
  • 3 algorithms
  • 3 complexity
  • 2 Public transportation
  • Show More...

  • Refine by Type
  • 22 document

  • Refine by Publication Year
  • 13 2014
  • 2 2015
  • 2 2018
  • 1 2008
  • 1 2010
  • Show More...

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