6 Search Results for "Fischer, Frank"


Document
Track A: Algorithms, Complexity and Games
Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring

Authors: Aleksander B. G. Christiansen and Eva Rotenberg

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
The arboricity α of a graph is the smallest number of forests necessary to cover its edges, and an arboricity decomposition of a graph is a decomposition of its edges into forests. The best near-linear time algorithm for arboricity decomposition guarantees at most α +2 forests if the graph has arboricity α (Blumenstock and Fischer [Markus Blumenstock and Frank Fischer, 2020]). In this paper, we study arboricity decomposition for dynamic graphs, that is, graphs that are subject to insertions and deletions of edges. We give an algorithm that, provided the arboricity of the dynamic graph never exceeds α, maintains an α+2 arboricity decomposition of the graph in poly(log n,α) update time, thus matching the number of forests currently obtainable in near-linear time for static (non-changing) graphs. Our construction goes via dynamic bounded out-degree orientations, and we present a fully-dynamic algorithm that explicitly orients the edges of the dynamic graph, such that no vertex has an out-degree exceeding ⌊ (1+ε)α ⌋ + 2. Our algorithm is deterministic and has a worst-case update time of O(ε^{-6}α² log³ n). The state-of-the-art explicit, deterministic, worst-case algorithm for bounded out-degree orientations maintains a β⋅ α + log_β n out-orientation in O(β²α²+βαlog_β n) time [Tsvi Kopelowitz et al., 2014]. As a consequence, we get an algorithm that maintains an implicit vertex colouring with 4⋅ 2^α colours, in amortised poly-log n update time, and with O(α log n) worst-case query time. Thus, at the expense of log n-factors in the update time, we improve on the number of colours from 2^O(α) to O(2^α) compared to the state-of-the-art for implicit dynamic colouring [Monika Henzinger et al., 2020].

Cite as

Aleksander B. G. Christiansen and Eva Rotenberg. Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{christiansen_et_al:LIPIcs.ICALP.2022.42,
  author =	{Christiansen, Aleksander B. G. and Rotenberg, Eva},
  title =	{{Fully-Dynamic \alpha + 2 Arboricity Decompositions and Implicit Colouring}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.42},
  URN =		{urn:nbn:de:0030-drops-163835},
  doi =		{10.4230/LIPIcs.ICALP.2022.42},
  annote =	{Keywords: Dynamic graphs, bounded arboricity, graph colouring, data structures}
}
Document
Strong Relaxations for the Train Timetabling Problem Using Connected Configurations

Authors: Frank Fischer and Thomas Schlechte

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)


Abstract
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.

Cite as

Frank Fischer and Thomas Schlechte. Strong Relaxations for the Train Timetabling Problem Using Connected Configurations. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2017.11,
  author =	{Fischer, Frank and Schlechte, Thomas},
  title =	{{Strong Relaxations for the Train Timetabling Problem Using Connected Configurations}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.11},
  URN =		{urn:nbn:de:0030-drops-79021},
  doi =		{10.4230/OASIcs.ATMOS.2017.11},
  annote =	{Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, connected configurations}
}
Document
Locality via Partially Lifted Codes

Authors: S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)


Abstract
In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data. In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP). This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large - a very strong guarantee - and Locally Recoverable Codes (LRCs) when s is small - a relatively weaker guarantee. This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper. We construct codes in this parameter regime which have a higher rate than previously known codes. Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan. Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.

Cite as

S. Luna Frank-Fischer, Venkatesan Guruswami, and Mary Wootters. Locality via Partially Lifted Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{frankfischer_et_al:LIPIcs.APPROX-RANDOM.2017.43,
  author =	{Frank-Fischer, S. Luna and Guruswami, Venkatesan and Wootters, Mary},
  title =	{{Locality via Partially Lifted Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.43},
  URN =		{urn:nbn:de:0030-drops-75922},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.43},
  annote =	{Keywords: Error correcting codes, locality, lifted codes}
}
Document
Ordering Constraints in Time Expanded Networks for Train Timetabling Problems

Authors: Frank Fischer

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


Abstract
The task of the train timetabling problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. This kind of problem has proven to be very challenging and numerous solution approaches have been proposed. One of the most successful approaches is based on time discretized network models. However, one of the major weaknesses of these models is that fractional solutions tend to change the order of trains along some track, which is not allowed for integer solutions, leading to poor relaxations. In this paper, we present an extension for these kind of models, which aims at overcoming these problems. By exploiting a configuration based formulation, we propose to extend the model with additional ordering constraints. These constraints enforce compatibility of orderings along a sequence of tracks and greatly improve the quality of the relaxations. We show in some promising preliminary computational experiments that our approach indeed helps to resolve many of the invalid overtaking problems of relaxations for the standard models.

Cite as

Frank Fischer. Ordering Constraints in Time Expanded Networks for Train Timetabling Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 97-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{fischer:OASIcs.ATMOS.2015.97,
  author =	{Fischer, Frank},
  title =	{{Ordering Constraints in Time Expanded Networks for Train Timetabling Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{97--110},
  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.97},
  URN =		{urn:nbn:de:0030-drops-54524},
  doi =		{10.4230/OASIcs.ATMOS.2015.97},
  annote =	{Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, ordering constraints}
}
Document
Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling

Authors: Frank Fischer and Christoph Helmberg

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


Abstract
The aim of the train timetabling problem is to find a conflict free timetable for a set of passenger and freight trains along their routes in an infrastructure network. Several constraints like station capacities and train dependent running and headway times have to be satisfied. In this work we deal with large scale instances of the aperiodic train timetabling problem for the German railway network. The problem is modelled in a classical way via time discretised networks, its Lagrange-dual is solved by a bundle method. In order to handle the enormous number of variables and constraints dynamic graph generation and dynamic rolling horizon techniques are employed.

Cite as

Frank Fischer and Christoph Helmberg. Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 45-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2010.45,
  author =	{Fischer, Frank and Helmberg, Christoph},
  title =	{{Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{45--60},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.45},
  URN =		{urn:nbn:de:0030-drops-27492},
  doi =		{10.4230/OASIcs.ATMOS.2010.45},
  annote =	{Keywords: combinatorial optimization, train-timetabling}
}
Document
Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

Authors: Frank Fischer, Christoph Helmberg, Jürgen Janßen, and Boris Krostitz

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


Abstract
The train timetabling problem considered is to find conflict free routes for a set of trains in a given railway network so that cer- tain time window conditions are satisfied. We deal with the very large scale problem of constructing such timetables for the German railway network. A number of restrictions on different train types like freight trains or passenger trains have to be observed, e.g., sequence dependent headway times, station capacities, and stopping times. In order to handle the enormous number of variables and constraints we employ Lagrangian relaxation of the conflict constraints combined with a cutting plane approach. The model is solved by a bundle method; its primal aggregate is used for separation and as starting point for rounding heuristics. We present some promising results towards handling a test instance com- prising ten percent of the entire network.

Cite as

Frank Fischer, Christoph Helmberg, Jürgen Janßen, and Boris Krostitz. Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2008.1585,
  author =	{Fischer, Frank and Helmberg, Christoph and Jan{\ss}en, J\"{u}rgen and Krostitz, Boris},
  title =	{{Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--12},
  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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1585},
  URN =		{urn:nbn:de:0030-drops-15850},
  doi =		{10.4230/OASIcs.ATMOS.2008.1585},
  annote =	{Keywords: }
}
  • Refine by Author
  • 4 Fischer, Frank
  • 2 Helmberg, Christoph
  • 1 Christiansen, Aleksander B. G.
  • 1 Frank-Fischer, S. Luna
  • 1 Guruswami, Venkatesan
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Dynamic graph algorithms

  • Refine by Keyword
  • 3 combinatorial optimization
  • 2 Lagrangian relaxation
  • 2 train timetabling
  • 1 Dynamic graphs
  • 1 Error correcting codes
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2017
  • 1 2008
  • 1 2010
  • 1 2015
  • 1 2022

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