Search Results

Documents authored by Widmayer, Peter

Document
DOI: 10.4230/OASIcs.ATMOS.2015.68
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.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
DOI: 10.4230/OASIcs.ATMOS.2013.27
Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations

Authors: Katerina Böhmová, Matús Mihalák, Tobias Pröger, Rastislav Srámek, and Peter Widmayer

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
We study the problem of robust routing in urban public transportation networks. In order to propose solutions that are robust for typical delays, we assume that we have past observations of real traffic situations available. In particular, we assume that we have "daily records" containing the observed travel times in the whole network for a few past days. We introduce a new concept to express a solution that is feasible in any record of a given public transportation network. We adapt the method of Buhmann et al. [Buhmann et al., ITCS 2013] for optimization under uncertainty, and develop algorithms that allow its application for finding a robust journey from a given source to a given destination. The performance of the algorithms and the quality of the predicted journey are evaluated in a preliminary experimental study. We furthermore introduce a measure of reliability of a given journey, and develop algorithms for its computation. The robust routing concepts presented in this work are suited specially for public transportation networks of large cities that lack clear hierarchical structure and contain services that run with high frequencies.
Cite as

Katerina Böhmová, Matús Mihalák, Tobias Pröger, Rastislav Srámek, and Peter Widmayer. Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 27-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bohmova_et_al:OASIcs.ATMOS.2013.27,
  author =	{B\"{o}hmov\'{a}, Katerina and Mihal\'{a}k, Mat\'{u}s and Pr\"{o}ger, Tobias and Sr\'{a}mek, Rastislav and Widmayer, Peter},
  title =	{{Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--41},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.27},
  URN =		{urn:nbn:de:0030-drops-42428},
  doi =		{10.4230/OASIcs.ATMOS.2013.27},
  annote =	{Keywords: Algorithms, Optimization, Robustness, Route planning, Public transportation}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2008
OASIcs, Volume 9, ATMOS'08, Complete Volume

Authors: Matteo Fischetti and Peter Widmayer

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
OASIcs, Volume 9, ATMOS'08, Complete Volume
Cite as

8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{fischetti_et_al:OASIcs.ATMOS.2008,
  title =	{{OASIcs, Volume 9, ATMOS'08, Complete Volume}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008},
  URN =		{urn:nbn:de:0030-drops-35712},
  doi =		{10.4230/OASIcs.ATMOS.2008},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Graph Theory, Applications}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.153
Telling convex from reflex allows to map a polygon

Authors: Jeremie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak, and Peter Widmayer

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

Abstract
We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other, i.e.~if the line segment connecting them lies inside $P$ entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counter-clockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (<= pi) or reflex (> pi). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known and show that the robot is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable and deterministic such robots can always position themselves such that they mutually see each other, i.e. such that they form a clique in the visibility graph.
Cite as

Jeremie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak, and Peter Widmayer. Telling convex from reflex allows to map a polygon. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 153-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.STACS.2011.153,
  author =	{Chalopin, Jeremie and Das, Shantanu and Disser, Yann and Mihalak, Matus and Widmayer, Peter},
  title =	{{Telling convex from reflex allows to map a polygon}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{153--164},
  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.153},
  URN =		{urn:nbn:de:0030-drops-30077},
  doi =		{10.4230/LIPIcs.STACS.2011.153},
  annote =	{Keywords: polygon mapping, map construction, autonomous agent, simple robot, visibility graph reconstruction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.61
Vertex Disjoint Paths for Dispatching in Railways

Authors: Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.
Cite as

Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych. Vertex Disjoint Paths for Dispatching in Railways. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 61-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{flier_et_al:OASIcs.ATMOS.2010.61,
  author =	{Flier, Holger and Mihal\'{a}k, Mat\'{u}s and Sch\"{o}bel, Anita and Widmayer, Peter and Zych, Anna},
  title =	{{Vertex Disjoint Paths for Dispatching in Railways}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{61--73},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.61},
  URN =		{urn:nbn:de:0030-drops-27508},
  doi =		{10.4230/OASIcs.ATMOS.2010.61},
  annote =	{Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2008.1592
ATMOS 2008 Abstracts Collection -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Matteo Fischetti and Peter Widmayer

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, held on Septmeber 18 in Karlsruhe, Germany.
Cite as

8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fischetti_et_al:OASIcs.ATMOS.2008.1592,
  author =	{Fischetti, Matteo and Widmayer, Peter},
  title =	{{ATMOS 2008 Abstracts Collection -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{i--vii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1592},
  URN =		{urn:nbn:de:0030-drops-15920},
  doi =		{10.4230/OASIcs.ATMOS.2008.1592},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1593
ATMOS 2008 Preface -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Authors: Matteo Fischetti and Peter Widmayer

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
The 8th ATMOS workshop was held in Karlsruhe, September 18, 2008, within ALGO, a set of meetings related to algorithms. The series of ATMOS workshops, starting in Heraklion in 2001, continuing in Malaga in 2002, Budapest in 2003, Bergen in 2004, Palma de Mallorca in 2005, Zurich in 2006, and Sevilla in 2007 is by now an established series of meetings between algorithms researchers dealing with transportation problems, and practitioners, mainly from railways.
Cite as

Matteo Fischetti and Peter Widmayer. ATMOS 2008 Preface -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fischetti_et_al:OASIcs.ATMOS.2008.1593,
  author =	{Fischetti, Matteo and Widmayer, Peter},
  title =	{{ATMOS 2008 Preface -- 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--5},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1593},
  URN =		{urn:nbn:de:0030-drops-15936},
  doi =		{10.4230/OASIcs.ATMOS.2008.1593},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.07151.1
07151 Abstracts Collection – Geometry in Sensor Networks

Authors: Subhash Suri, Roger Wattenhofer, and Peter Widmayer

Published in: Dagstuhl Seminar Proceedings, Volume 7151, Geometry in Sensor Networks (2007)

Abstract
From 9.4.2007 to 13.4.07, the Dagstuhl Seminar 07151 ``Geometry in Sensor Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Subhash Suri, Roger Wattenhofer, and Peter Widmayer. 07151 Abstracts Collection – Geometry in Sensor Networks. In Geometry in Sensor Networks. Dagstuhl Seminar Proceedings, Volume 7151, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{suri_et_al:DagSemProc.07151.1,
  author =	{Suri, Subhash and Wattenhofer, Roger and Widmayer, Peter},
  title =	{{07151 Abstracts Collection – Geometry in Sensor Networks}},
  booktitle =	{Geometry in Sensor Networks},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7151},
  editor =	{Subhash Suri and Roger Wattenhofer and Peter Widmayer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07151.1},
  URN =		{urn:nbn:de:0030-drops-11206},
  doi =		{10.4230/DagSemProc.07151.1},
  annote =	{Keywords: Sensor networks, computational geometry, distributed algorithms, mobile computing}
}
Document
DOI: 10.4230/DagSemRep.335
Data Structures (Dagstuhl Seminar 02091)

Authors: Susanne Albers, Robert Sedgewick, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Robert Sedgewick, and Peter Widmayer. Data Structures (Dagstuhl Seminar 02091). Dagstuhl Seminar Report 335, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.335,
  author =	{Albers, Susanne and Sedgewick, Robert and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 02091)}},
  pages =	{1--36},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{335},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.335},
  URN =		{urn:nbn:de:0030-drops-152176},
  doi =		{10.4230/DagSemRep.335},
}
Document
DOI: 10.4230/DagSemRep.267
Data Structures (Dagstuhl Seminar 00091)

Authors: Susanne Albers, Ian Munro, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Susanne Albers, Ian Munro, and Peter Widmayer. Data Structures (Dagstuhl Seminar 00091). Dagstuhl Seminar Report 267, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.267,
  author =	{Albers, Susanne and Munro, Ian and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 00091)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{267},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.267},
  URN =		{urn:nbn:de:0030-drops-151525},
  doi =		{10.4230/DagSemRep.267},
}
Document
DOI: 10.4230/DagSemRep.202
Data Structures (Dagstuhl Seminar 98091)

Authors: Ian Munro, Stefan Näher, and Peter Widmayer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Ian Munro, Stefan Näher, and Peter Widmayer. Data Structures (Dagstuhl Seminar 98091). Dagstuhl Seminar Report 202, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{munro_et_al:DagSemRep.202,
  author =	{Munro, Ian and N\"{a}her, Stefan and Widmayer, Peter},
  title =	{{Data Structures (Dagstuhl Seminar 98091)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{202},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.202},
  URN =		{urn:nbn:de:0030-drops-150881},
  doi =		{10.4230/DagSemRep.202},
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact