Search Results

Documents authored by Seebach, Constantin

Document
DOI: 10.4230/OASIcs.ATMOS.2023.4
Non-Pool-Based Line Planning on Graphs of Bounded Treewidth

Authors: Irene Heinrich, Philine Schiewe, and Constantin Seebach

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
Line planning, i.e. choosing routes which are to be serviced by vehicles in order to satisfy network demands, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical investigations consider the problem of choosing lines only from a predefined line pool. We consider the line planning problem when all simple paths can be used as lines and present an algorithm which is fixed-parameter tractable, i.e. it is efficient on instances with small parameter. As a parameter we consider the treewidth of the public transport network, along with its maximum degree as well as the maximum allowed frequency.
Cite as

Irene Heinrich, Philine Schiewe, and Constantin Seebach. Non-Pool-Based Line Planning on Graphs of Bounded Treewidth. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:OASIcs.ATMOS.2023.4,
  author =	{Heinrich, Irene and Schiewe, Philine and Seebach, Constantin},
  title =	{{Non-Pool-Based Line Planning on Graphs of Bounded Treewidth}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{4:1--4:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.4},
  URN =		{urn:nbn:de:0030-drops-187656},
  doi =		{10.4230/OASIcs.ATMOS.2023.4},
  annote =	{Keywords: line planning, public transport, treewidth, integer programming, fixed parameter tractability}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.8
Algorithms and Hardness for Non-Pool-Based Line Planning

Authors: Irene Heinrich, Philine Schiewe, and Constantin Seebach

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

Abstract
Line planning, i.e. choosing paths which are operated by one vehicle end-to-end, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical observations consider the problem of choosing lines from a predefined line pool. In this paper, we consider the complexity of the line planning problem when all simple paths can be used as lines. Depending on the cost structure, we show that the problem can be NP-hard even for paths and stars, and that no polynomial time approximation of sub-linear performance is possible. Additionally, we identify polynomially solvable cases and present a pseudo-polynomial solution approach for trees.
Cite as

Irene Heinrich, Philine Schiewe, and Constantin Seebach. Algorithms and Hardness for Non-Pool-Based Line Planning. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:OASIcs.ATMOS.2022.8,
  author =	{Heinrich, Irene and Schiewe, Philine and Seebach, Constantin},
  title =	{{Algorithms and Hardness for Non-Pool-Based Line Planning}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{8:1--8:21},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.8},
  URN =		{urn:nbn:de:0030-drops-171124},
  doi =		{10.4230/OASIcs.ATMOS.2022.8},
  annote =	{Keywords: line planning, public transport, discrete optimization, complexity, algorithm design}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.58
Resolution with Symmetry Rule Applied to Linear Equations

Authors: Pascal Schweitzer and Constantin Seebach

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
This paper considers the length of resolution proofs when using Krishnamurthy’s classic symmetry rules. We show that inconsistent linear equation systems of bounded width over a fixed finite field 𝔽_p with p a prime have, in their standard encoding as CNFs, polynomial length resolutions when using the local symmetry rule (SRC-II). As a consequence it follows that the multipede instances for the graph isomorphism problem encoded as CNF formula have polynomial length resolution proofs. This contrasts exponential lower bounds for individualization-refinement algorithms on these graphs. For the Cai-Fürer-Immerman graphs, for which Torán showed exponential lower bounds for resolution proofs (SAT 2013), we also show that already the global symmetry rule (SRC-I) suffices to allow for polynomial length proofs.
Cite as

Pascal Schweitzer and Constantin Seebach. Resolution with Symmetry Rule Applied to Linear Equations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{schweitzer_et_al:LIPIcs.STACS.2021.58,
  author =	{Schweitzer, Pascal and Seebach, Constantin},
  title =	{{Resolution with Symmetry Rule Applied to Linear Equations}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.58},
  URN =		{urn:nbn:de:0030-drops-137038},
  doi =		{10.4230/LIPIcs.STACS.2021.58},
  annote =	{Keywords: Logical Resolution, Symmetry Rule, Linear Equation System}
}
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