80 Search Results for "M�ller-Hannemann, Matthias"


Volume

OASIcs, Volume 96

21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

ATMOS 2021, September 9-10, 2021, Lisbon, Portugal (Virtual Conference)

Editors: Matthias Müller-Hannemann and Federico Perea

Volume

OASIcs, Volume 5

6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)

ATMOS 2006, September 14, 2006, Zuerich, Switzerland

Editors: Riko Jacob and Matthias Müller-Hannemann

Document
Quantum Event Learning and Gentle Random Measurements

Authors: Adam Bene Watts and John Bostanci

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
We prove the expected disturbance caused to a quantum system by a sequence of randomly ordered two-outcome projective measurements is upper bounded by the square root of the probability that at least one measurement in the sequence accepts. We call this bound the Gentle Random Measurement Lemma. We then extend the techniques used to prove this lemma to develop protocols for problems in which we are given sample access to an unknown state ρ and asked to estimate properties of the accepting probabilities Tr[M_i ρ] of a set of measurements {M₁, M₂, … , M_m}. We call these types of problems Quantum Event Learning Problems. In particular, we show randomly ordering projective measurements solves the Quantum OR problem, answering an open question of Aaronson. We also give a Quantum OR protocol which works on non-projective measurements and which outperforms both the random measurement protocol analyzed in this paper and the protocol of Harrow, Lin, and Montanaro. However, this protocol requires a more complicated type of measurement, which we call a Blended Measurement. Given additional guarantees on the set of measurements {M₁, …, M_m}, we show the random and blended measurement Quantum OR protocols developed in this paper can also be used to find a measurement M_i such that Tr[M_i ρ] is large. We call the problem of finding such a measurement Quantum Event Finding. We also show Blended Measurements give a sample-efficient protocol for Quantum Mean Estimation: a problem in which the goal is to estimate the average accepting probability of a set of measurements on an unknown state. Finally we consider the Threshold Search Problem described by O'Donnell and Bădescu where, given given a set of measurements {M₁, …, M_m} along with sample access to an unknown state ρ satisfying Tr[M_i ρ] ≥ 1/2 for some M_i, the goal is to find a measurement M_j such that Tr[M_j ρ] ≥ 1/2 - ε. By building on our Quantum Event Finding result we show that randomly ordered (or blended) measurements can be used to solve this problem using O(log²(m) / ε²) copies of ρ. This matches the performance of the algorithm given by O'Donnell and Bădescu, but does not require injected noise in the measurements. Consequently, we obtain an algorithm for Shadow Tomography which matches the current best known sample complexity (i.e. requires Õ(log²(m)log(d)/ε⁴) samples). This algorithm does not require injected noise in the quantum measurements, but does require measurements to be made in a random order, and so is no longer online.

Cite as

Adam Bene Watts and John Bostanci. Quantum Event Learning and Gentle Random Measurements. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 97:1-97:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{watts_et_al:LIPIcs.ITCS.2024.97,
  author =	{Watts, Adam Bene and Bostanci, John},
  title =	{{Quantum Event Learning and Gentle Random Measurements}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{97:1--97:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.97},
  URN =		{urn:nbn:de:0030-drops-196254},
  doi =		{10.4230/LIPIcs.ITCS.2024.97},
  annote =	{Keywords: Event learning, gentle measurments, random measurements, quantum or, threshold search, shadow tomography}
}
Document
Cluster Editing with Overlapping Communities

Authors: Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example, in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Another strong motivation comes from language networks where trying to cluster words with similar usage can be confounded by homonyms, that is, words with multiple meanings like "bat". The recently introduced operation of vertex splitting is one natural approach to incorporating such overlap into Cluster Editing. First used in the context of graph drawing, this operation allows a vertex v to be replaced by two vertices whose combined neighborhood is the neighborhood of v (and thus v can belong to more than one cluster). The problem of transforming a graph into a cluster graph using at most k edge additions, edge deletions, or vertex splits is called Cluster Editing with Vertex Splitting and is known to admit a polynomial kernel with respect to k and an O(9^{k²} + n + m)-time (parameterized) algorithm. However, it was not known whether the problem is NP-hard, a question which was originally asked by Abu-Khzam et al. [Combinatorial Optimization, 2018]. We answer this in the affirmative. We further give an improved algorithm running in O(2^{7klog k} + n + m) time.

Cite as

Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2,
  author =	{Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra},
  title =	{{Cluster Editing with Overlapping Communities}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2},
  URN =		{urn:nbn:de:0030-drops-194218},
  doi =		{10.4230/LIPIcs.IPEC.2023.2},
  annote =	{Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm}
}
Document
On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model

Authors: Matthias Bentert, Jannik Schestag, and Frank Sommer

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph G = (V,E) in which the edge set E is partitioned into a set S of safe edges and a set U of unsafe edges and the task is to find a set T of at most k edges such that T - {u} is connected and spans V for any unsafe edge u ∈ T. Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.

Cite as

Matthias Bentert, Jannik Schestag, and Frank Sommer. On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.IPEC.2023.4,
  author =	{Bentert, Matthias and Schestag, Jannik and Sommer, Frank},
  title =	{{On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.4},
  URN =		{urn:nbn:de:0030-drops-194232},
  doi =		{10.4230/LIPIcs.IPEC.2023.4},
  annote =	{Keywords: Flexible graph connectivity, NP-hard problem, parameterized complexity, below-guarantee parameterization, treewidth}
}
Document
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Authors: Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett. , 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m⋅log(4mΔ), where m is the number of constraints, and Δ is the largest absolute coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m⋅(log(3A_max)+√{log(A_max)}), where A_max≔ ‖A‖₁ denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m⋅log(1.46 A_max). Our upper bounds also hold with A_max replaced by √mΔ, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||C_{max}). Our EPTAS yields a (1+ε)-approximation for Q||C_{max} on N jobs in time 2^𝒪(1/ε log³(1/ε)log(log(1/ε))) + 𝒪(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^𝒪(1/ε log⁴(1/ε)) + N^𝒪(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||C_max, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.

Cite as

Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, and Tobias Stamm. New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ISAAC.2023.13,
  author =	{Berndt, Sebastian and Brinkop, Hauke and Jansen, Klaus and Mnich, Matthias and Stamm, Tobias},
  title =	{{New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.13},
  URN =		{urn:nbn:de:0030-drops-193155},
  doi =		{10.4230/LIPIcs.ISAAC.2023.13},
  annote =	{Keywords: Integer programming, scheduling algorithms, uniformly related machines, makespan minimization}
}
Document
A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots

Authors: Max Deppert, Matthias Kaul, and Matthias Mnich

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v₀, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2-1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of n^Θ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the n^Θ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/ε)^O(dlog d) ⋅ n^O(1), and produces a (3/2+ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2^d ⋅ n^O(1).

Cite as

Max Deppert, Matthias Kaul, and Matthias Mnich. A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.ESA.2023.39,
  author =	{Deppert, Max and Kaul, Matthias and Mnich, Matthias},
  title =	{{A (3/2 + \epsilon)-Approximation for Multiple TSP with a Variable Number of Depots}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.39},
  URN =		{urn:nbn:de:0030-drops-186925},
  doi =		{10.4230/LIPIcs.ESA.2023.39},
  annote =	{Keywords: Traveling salesperson problem, rural postperson problem, multiple TSP, vehicle routing}
}
Document
Passenger-Aware Real-Time Planning of Short Turns to Reduce Delays in Public Transport

Authors: Julian Patzner, Ralf Rückert, and Matthias Müller-Hannemann

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)


Abstract
Delays and disruptions are commonplace in public transportation. An important tool to limit the impact of severely delayed vehicles is the use of short turns, where a planned trip is shortened in order to be able to resume the following trip in the opposite direction as close to the schedule as possible. Short turns have different effects on passengers: some suffer additional delays and have to reschedule their route, while others can benefit from them. Dispatchers therefore need decision support in order to use short turns only if the overall delay of all affected passengers is positively influenced. In this paper, we study the planning of short turns based on passenger flows. We propose a simulation framework which can be used to decide upon single short turns in real time. An experimental study with a scientific model (LinTim) of an entire public transport system for the German city of Stuttgart including busses, trams, and local trains shows that we can solve these problems on average within few milliseconds. Based on features of the current delay scenario and the passenger flow we use machine learning to classify cases where short turns are beneficial. Depending on how many features are used, we reach a correct classification rate of more than 93% (full feature set) and 90% (partial feature set) using random forests. Since precise passenger flows are often not available in urban public transportation, our machine learning approach has the great advantage of working with significantly less detailed passenger information.

Cite as

Julian Patzner, Ralf Rückert, and Matthias Müller-Hannemann. Passenger-Aware Real-Time Planning of Short Turns to Reduce Delays in Public Transport. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{patzner_et_al:OASIcs.ATMOS.2022.13,
  author =	{Patzner, Julian and R\"{u}ckert, Ralf and M\"{u}ller-Hannemann, Matthias},
  title =	{{Passenger-Aware Real-Time Planning of Short Turns to Reduce Delays in Public Transport}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{13:1--13:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.13},
  URN =		{urn:nbn:de:0030-drops-171171},
  doi =		{10.4230/OASIcs.ATMOS.2022.13},
  annote =	{Keywords: Public Transportation, Delays, Real-time Dispatching, Passenger Flows}
}
Document
Computing a Link Diagram from Its Exterior

Authors: Nathan M. Dunfield, Malik Obeidin, and Cameron Gates Rudd

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
A knot is a circle piecewise-linearly embedded into the 3-sphere. The topology of a knot is intimately related to that of its exterior, which is the complement of an open regular neighborhood of the knot. Knots are typically encoded by planar diagrams, whereas their exteriors, which are compact 3-manifolds with torus boundary, are encoded by triangulations. Here, we give the first practical algorithm for finding a diagram of a knot given a triangulation of its exterior. Our method applies to links as well as knots, and allows us to recover links with hundreds of crossings. We use it to find the first diagrams known for 23 principal congruence arithmetic link exteriors; the largest has over 2,500 crossings. Other applications include finding pairs of knots with the same 0-surgery, which relates to questions about slice knots and the smooth 4D Poincaré conjecture.

Cite as

Nathan M. Dunfield, Malik Obeidin, and Cameron Gates Rudd. Computing a Link Diagram from Its Exterior. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 37:1-37:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dunfield_et_al:LIPIcs.SoCG.2022.37,
  author =	{Dunfield, Nathan M. and Obeidin, Malik and Rudd, Cameron Gates},
  title =	{{Computing a Link Diagram from Its Exterior}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{37:1--37:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.37},
  URN =		{urn:nbn:de:0030-drops-160457},
  doi =		{10.4230/LIPIcs.SoCG.2022.37},
  annote =	{Keywords: computational topology, low-dimensional topology, knot, knot exterior, knot diagram, link, link exterior, link diagram}
}
Document
Complete Volume
OASIcs, Volume 96, ATMOS 2021, Complete Volume

Authors: Matthias Müller-Hannemann and Federico Perea

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
OASIcs, Volume 96, ATMOS 2021, Complete Volume

Cite as

21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@Proceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021,
  title =	{{OASIcs, Volume 96, ATMOS 2021, Complete Volume}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{1--304},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021},
  URN =		{urn:nbn:de:0030-drops-148685},
  doi =		{10.4230/OASIcs.ATMOS.2021},
  annote =	{Keywords: OASIcs, Volume 96, ATMOS 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Matthias Müller-Hannemann and Federico Perea

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.0,
  author =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.0},
  URN =		{urn:nbn:de:0030-drops-148690},
  doi =		{10.4230/OASIcs.ATMOS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes

Authors: Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.

Cite as

Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe. Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{sartori_et_al:OASIcs.ATMOS.2021.1,
  author =	{Sartori, Carlo S. and Smet, Pieter and Vanden Berghe, Greet},
  title =	{{Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.1},
  URN =		{urn:nbn:de:0030-drops-148703},
  doi =		{10.4230/OASIcs.ATMOS.2021.1},
  annote =	{Keywords: Vehicle scheduling, Workload balancing, Route duration, Interdependent routes, Time windows}
}
Document
Forward Cycle Bases and Periodic Timetabling

Authors: Niels Lindner, Christian Liebchen, and Berenike Masing

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.

Cite as

Niels Lindner, Christian Liebchen, and Berenike Masing. Forward Cycle Bases and Periodic Timetabling. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.2,
  author =	{Lindner, Niels and Liebchen, Christian and Masing, Berenike},
  title =	{{Forward Cycle Bases and Periodic Timetabling}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{2:1--2:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.2},
  URN =		{urn:nbn:de:0030-drops-148719},
  doi =		{10.4230/OASIcs.ATMOS.2021.2},
  annote =	{Keywords: Periodic Timetabling, Cycle Bases, Mixed Integer Programming}
}
Document
Towards Improved Robustness of Public Transport by a Machine-Learned Oracle

Authors: Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive. For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.

Cite as

Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Towards Improved Robustness of Public Transport by a Machine-Learned Oracle. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.3,
  author =	{M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Towards Improved Robustness of Public Transport by a Machine-Learned Oracle}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{3:1--3:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.3},
  URN =		{urn:nbn:de:0030-drops-148721},
  doi =		{10.4230/OASIcs.ATMOS.2021.3},
  annote =	{Keywords: Public Transportation, Timetabling, Machine Learning, Robustness}
}
Document
Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties

Authors: Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo, and Akshay Gupte

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)


Abstract
The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages before the actual service. Our two-stage heuristic is competitive to CPLEX’s exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.

Cite as

Syu-Ning Johnn, Yiran Zhu, Andrés Miniguano-Trujillo, and Akshay Gupte. Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{johnn_et_al:OASIcs.ATMOS.2021.4,
  author =	{Johnn, Syu-Ning and Zhu, Yiran and Miniguano-Trujillo, Andr\'{e}s and Gupte, Akshay},
  title =	{{Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) Problem with Uncertainties}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{4:1--4:21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.4},
  URN =		{urn:nbn:de:0030-drops-148737},
  doi =		{10.4230/OASIcs.ATMOS.2021.4},
  annote =	{Keywords: Home Health Care, Mixed-Integer Linear Programming, Two-stage Stochastic, Uncertainties A Priori Optimisation, Adaptive Large Neighbourhood Search, Monte-Carlo Simulation}
}
  • Refine by Author
  • 20 Müller-Hannemann, Matthias
  • 8 Schöbel, Anita
  • 7 Mnich, Matthias
  • 7 Rückert, Ralf
  • 3 Bentert, Matthias
  • Show More...

  • Refine by Classification
  • 14 Applied computing → Transportation
  • 7 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Graph algorithms analysis
  • 3 Mathematics of computing → Graph theory
  • 3 Mathematics of computing → Mathematical optimization
  • Show More...

  • Refine by Keyword
  • 3 Timetable information system
  • 3 passenger flows
  • 2 Algorithms and data structures
  • 2 Line Planning
  • 2 Network Design
  • Show More...

  • Refine by Type
  • 78 document
  • 2 volume

  • Refine by Publication Year
  • 25 2021
  • 15 2006
  • 4 2008
  • 4 2016
  • 4 2023
  • 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