9 Search Results for "P�tzold, Julius"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.44
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP

Authors: Fabian Egidy, Christian Glaßer, and Martin Herold

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over NP. Our main results concern DP, i.e., the second level of this hierarchy: - If all sets in DP have p-optimal proof systems, then all sets in coDP have p-optimal proof systems. - The analogous implication for optimal proof systems fails relative to an oracle. As a consequence, we clarify such implications for all classes 𝒞 and 𝒟 in the Boolean hierarchy over NP: either we can prove the implication or show that it fails relative to an oracle. Furthermore, we show that the sets SAT and TAUT have p-optimal proof systems, if and only if all sets in the Boolean hierarchy over NP have p-optimal proof systems which is a new characterization of a conjecture studied by Pudlák.
Cite as

Fabian Egidy, Christian Glaßer, and Martin Herold. Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{egidy_et_al:LIPIcs.MFCS.2023.44,
  author =	{Egidy, Fabian and Gla{\ss}er, Christian and Herold, Martin},
  title =	{{Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{44:1--44:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.44},
  URN =		{urn:nbn:de:0030-drops-185784},
  doi =		{10.4230/LIPIcs.MFCS.2023.44},
  annote =	{Keywords: Computational Complexity, Boolean Hierarchy, Proof Complexity, Proof Systems, Oracle Construction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.45
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors: Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs. This contributes to a research program initiated by Pudlák [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.
Cite as

Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ehrmanntraut_et_al:LIPIcs.MFCS.2022.45,
  author =	{Ehrmanntraut, Anton and Egidy, Fabian and Gla{\ss}er, Christian},
  title =	{{Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45},
  URN =		{urn:nbn:de:0030-drops-168435},
  doi =		{10.4230/LIPIcs.MFCS.2022.45},
  annote =	{Keywords: computational complexity, promise classes, proof complexity, complete sets, oracle construction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.9
NP-Completeness, Proof Systems, and Disjoint NP-Pairs

Authors: Titus Dose and Christian Glaßer

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The article investigates the relation between three well-known hypotheses. - H_{union}: the union of disjoint ≤^p_m-complete sets for NP is ≤^p_m-complete - H_{opps}: there exist optimal propositional proof systems - H_{cpair}: there exist ≤^{pp}_m-complete disjoint NP-pairs The following results are obtained: - The hypotheses are pairwise independent under relativizable proofs, except for the known implication H_{opps} ⇒ H_{cpair}. - An answer to Pudlák’s question for an oracle relative to which ¬H_{cpair}, ¬H_{opps}, and UP has ≤^p_m-complete sets. - The converse of Köbler, Messner, and Torán’s implication NEE ∩ TALLY ⊆ coNEE ⇒ H_{opps} fails relative to an oracle, where NEE =^{df} NTIME(2^O(2ⁿ)). - New characterizations of H_{union} and two variants in terms of coNP-completeness and p-producibility of the set of hard formulas of propositional proof systems.
Cite as

Titus Dose and Christian Glaßer. NP-Completeness, Proof Systems, and Disjoint NP-Pairs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dose_et_al:LIPIcs.STACS.2020.9,
  author =	{Dose, Titus and Gla{\ss}er, Christian},
  title =	{{NP-Completeness, Proof Systems, and Disjoint NP-Pairs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.9},
  URN =		{urn:nbn:de:0030-drops-118707},
  doi =		{10.4230/LIPIcs.STACS.2020.9},
  annote =	{Keywords: NP-complete, propositional proof system, disjoint NP-pair, oracle}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.6
The Trickle-In Effect: Modeling Passenger Behavior in Delay Management

Authors: Anita Schöbel, Julius Pätzold, and Jörg P. Müller

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

Abstract
Delay management is concerned with making decisions if a train should wait for passengers from delayed trains or if it should depart on time. Models for delay management exist and can be adapted to capacities of stations, capacities of tracks, or respect vehicle and driver schedules, passengers' routes and further constraints. Nevertheless, what has been neglected so far, is that a train cannot depart as planned if passengers from another train trickle in one after another such that the doors of the departing train cannot close. This effect is often observed in real-world, but has not yet been taken into account in delay management. We show the impact of this "trickle-in" effect to departure delays of trains under different conditions. We then modify existing delay management models to take the trickle-in effect into account. This can be done by forbidding certain intervals for departure. We present an integer programming formulation with these additional constraints resulting in a generalization of classic delay management models. We analyze the resulting model and identify parameters with which it can be best approximated by the classical delay management problem. Experimentally, we show that the trickle-in effect has a high impact on the overall delay of public transport systems. We discuss the impact of the trickle-in effect on the objective function value and on the computation time of the delay management problem. We also analyze the trickle-in effect for timetables which have been derived without taking this particular behavioral pattern of passengers into account.
Cite as

Anita Schöbel, Julius Pätzold, and Jörg P. Müller. The Trickle-In Effect: Modeling Passenger Behavior in Delay Management. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schobel_et_al:OASIcs.ATMOS.2019.6,
  author =	{Sch\"{o}bel, Anita and P\"{a}tzold, Julius and M\"{u}ller, J\"{o}rg P.},
  title =	{{The Trickle-In Effect: Modeling Passenger Behavior in Delay Management}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{6:1--6:15},
  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.6},
  URN =		{urn:nbn:de:0030-drops-114187},
  doi =		{10.4230/OASIcs.ATMOS.2019.6},
  annote =	{Keywords: Public Transport Planning, Delay Management, Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.47
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle

Authors: Titus Dose

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Pudlák [P. Pudlák, 2017] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are: - DisjNP: The class of all disjoint NP-pairs has no many-one complete elements. - SAT: NP contains no many-one complete sets that have P-optimal proof systems. - UP: UP has no many-one complete problems. - NP cap coNP: NP cap coNP has no many-one complete problems. As one answer to this question, we construct an oracle relative to which DisjNP, neg SAT, UP, and NP cap coNP hold, i.e., there is no relativizable proof for the implication DisjNP wedge UP wedge NP cap coNP ==> SAT. In particular, regarding the conjectures by Pudlák this extends a result by Khaniki [Khaniki, 2019]. Since Khaniki [Khaniki, 2019] constructs an oracle showing that the implication SAT ==> DisjNP has no relativizable proof, we obtain that the conjectures DisjNP and SAT are independent in relativized worlds, i.e., none of the implications DisjNP ==> SAT and SAT ==> DisjNP can be proven relativizably.
Cite as

Titus Dose. P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dose:LIPIcs.MFCS.2019.47,
  author =	{Dose, Titus},
  title =	{{P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.47},
  URN =		{urn:nbn:de:0030-drops-109918},
  doi =		{10.4230/LIPIcs.MFCS.2019.47},
  annote =	{Keywords: NP-complete, proof systems, disjoint NP-pair, oracle, UP}
}
Document
DOI: 10.4230/OASIcs.WCET.2019.4
Worst-Case Energy-Consumption Analysis by Microarchitecture-Aware Timing Analysis for Device-Driven Cyber-Physical Systems

Authors: Phillip Raffeck, Christian Eichler, Peter Wägemann, and Wolfgang Schröder-Preikschat

Published in: OASIcs, Volume 72, 19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)

Abstract
Many energy-constrained cyber-physical systems require both timeliness and the execution of tasks within given energy budgets. That is, besides knowledge on worst-case execution time (WCET), the worst-case energy consumption (WCEC) of operations is essential. Unfortunately, WCET analysis approaches are not directly applicable for deriving WCEC bounds in device-driven cyber-physical systems: For example, a single memory operation can lead to a significant power-consumption increase when thereby switching on a device (e.g. transceiver, actuator) in the embedded system. However, as we demonstrate in this paper, existing approaches from microarchitecture-aware timing analysis (i.e. considering cache and pipeline effects) are beneficial for determining WCEC bounds: We extended our framework on whole-system analysis with microarchitecture-aware timing modeling to precisely account for the execution time that devices are kept (in)active. Our evaluations based on a benchmark generator, which is able to output benchmarks with known baselines (i.e. actual WCET and actual WCEC), and an ARM Cortex-M4 platform validate that the approach significantly reduces analysis pessimism in whole-system WCEC analyses.
Cite as

Phillip Raffeck, Christian Eichler, Peter Wägemann, and Wolfgang Schröder-Preikschat. Worst-Case Energy-Consumption Analysis by Microarchitecture-Aware Timing Analysis for Device-Driven Cyber-Physical Systems. In 19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019). Open Access Series in Informatics (OASIcs), Volume 72, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{raffeck_et_al:OASIcs.WCET.2019.4,
  author =	{Raffeck, Phillip and Eichler, Christian and W\"{a}gemann, Peter and Schr\"{o}der-Preikschat, Wolfgang},
  title =	{{Worst-Case Energy-Consumption Analysis by Microarchitecture-Aware Timing Analysis for Device-Driven Cyber-Physical Systems}},
  booktitle =	{19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)},
  pages =	{4:1--4:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-118-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{72},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2019.4},
  URN =		{urn:nbn:de:0030-drops-107699},
  doi =		{10.4230/OASIcs.WCET.2019.4},
  annote =	{Keywords: WCEC, WCRE, WCET, michroarchitecture analysis, whole-system analysis}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.8
Cost-Minimal Public Transport Planning

Authors: Julius Pätzold, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
In this paper we discuss what a cost-optimal public transport plan looks like, i.e., we determine a line plan, a timetable and a vehicle schedule which can be operated with minimal costs while, at the same time, allowing all passengers to travel between their origins and destinations. We are hereby interested in an exact solution of the integrated problem. In contrast to a passenger-optimal transport plan, in which there is a direct connection for every origin-destination pair, the structure or model for determining a cost-optimal transport plan is not obvious and has not been researched so far. We present three models which differ with respect to the structures we are looking for. If lines are directed and may contain circles, we prove that a cost-optimal schedule can (under weak assumptions) already be obtained by first distributing the passengers in a cost-optimal way. We are able to streamline the resulting integer program such that it can be applied to real-world instances. The model gives bounds for the general case. In the second model we look for lines operated in both directions, but allow only simplified vehicle schedules. This model then yields stronger bounds than the first one. Our most realistic model looks for lines operated in both directions, and allows all structures for the vehicle schedules. This model, however, is only computable for small instances. Finally, the results of the three models and their respective bounds are compared experimentally.
Cite as

Julius Pätzold, Alexander Schiewe, and Anita Schöbel. Cost-Minimal Public Transport Planning. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2018.8,
  author =	{P\"{a}tzold, Julius and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Cost-Minimal Public Transport Planning}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{8:1--8:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.8},
  URN =		{urn:nbn:de:0030-drops-97138},
  doi =		{10.4230/OASIcs.ATMOS.2018.8},
  annote =	{Keywords: Public Transport Planning, Integer Optimization, Line Planning, Vehicle Scheduling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.17
Look-Ahead Approaches for Integrated Planning in Public Transportation

Authors: Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel

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

Abstract
In this paper we deal with three consecutive planning stages in public transportation: Line planning (including line pool generation), timetabling, and vehicle scheduling. These three steps are traditionally performed one after another in a sequential way often leading to high costs in the (last) vehicle scheduling stage. In this paper we propose three different ways to "look ahead", i.e., to include aspects of vehicle scheduling already earlier in the sequential process: an adapted line pool generation algorithm, a new cost structure for line planning, and a reordering of the sequential planning stages. We analyze these enhancements experimentally and show that they can be used to decrease the costs significantly.
Cite as

Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2017.17,
  author =	{P\"{a}tzold, Julius and Schiewe, Alexander and Schiewe, Philine and Sch\"{o}bel, Anita},
  title =	{{Look-Ahead Approaches for Integrated Planning in Public Transportation}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{17:1--17: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.17},
  URN =		{urn:nbn:de:0030-drops-78944},
  doi =		{10.4230/OASIcs.ATMOS.2017.17},
  annote =	{Keywords: line pool generation, line planning, vehicle scheduling, integrated planning, public transport}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.1
A Matching Approach for Periodic Timetabling

Authors: Julius Pätzold and Anita Schöbel

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard, but with important applications mainly for finding good timetables in public transportation. In this paper we consider PESP in public transportation, but in a reduced version (r-PESP) in which the driving and waiting times of the vehicles are fixed to their lower bounds. This results in a still NP-hard problem which has less variables, since only one variable determines the schedule for a whole line. We propose a formulation for r-PESP which is based on scheduling the lines. This enables us on the one hand to identify a finite candidate set and an exact solution approach. On the other hand, we use this formulation to derive a matching-based heuristic for solving PESP. Our experiments on close to real-world instances from LinTim show that our heuristic is able to compute competitive timetables in a very short runtime.
Cite as

Julius Pätzold and Anita Schöbel. A Matching Approach for Periodic Timetabling. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2016.1,
  author =	{P\"{a}tzold, Julius and Sch\"{o}bel, Anita},
  title =	{{A Matching Approach for Periodic Timetabling}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.1},
  URN =		{urn:nbn:de:0030-drops-65251},
  doi =		{10.4230/OASIcs.ATMOS.2016.1},
  annote =	{Keywords: PESP, Timetabling, Public Transport, Matching, Finite Dominating Set}
}
  • Refine by Author
  • 4 Pätzold, Julius
  • 4 Schöbel, Anita
  • 3 Glaßer, Christian
  • 2 Dose, Titus
  • 2 Egidy, Fabian
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Oracles and decision trees
  • 4 Theory of computation → Proof complexity
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Applied computing → Transportation
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • Show More...

  • Refine by Keyword
  • 2 NP-complete
  • 2 Public Transport Planning
  • 2 disjoint NP-pair
  • 2 oracle
  • 1 Boolean Hierarchy
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2019
  • 1 2016
  • 1 2017
  • 1 2018
  • 1 2020
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact