2 Search Results for "Dück, Viktor"

Document
DOI: 10.4230/LIPIcs.FUN.2024.15
Polyamorous Scheduling

Authors: Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs. We formally define and study the underlying optimisation problem: Polyamorous Scheduling. In Polyamorous Scheduling, we are given an edge-weighted graph and try to find a periodic schedule of matchings in this graph such that the maximal weighted waiting time between consecutive occurrences of the same edge is minimised. We show that the problem is NP-hard and that there is no efficient approximation algorithm with a better ratio than 4/3 unless P = NP. On the positive side, we obtain an O(log n)-approximation algorithm; indeed, an O(log Δ)-approximation for Δ the maximum degree, i.e., the largest number of relationships of any individual. We also define a generalisation of density from the Pinwheel Scheduling Problem, "poly density", and ask whether there exists a poly-density threshold similar to the 5/6-density threshold for Pinwheel Scheduling [Kawamura, STOC 2024]. Polyamorous Scheduling is a natural generalisation of Pinwheel Scheduling with respect to its optimisation variant, Bamboo Garden Trimming. Our work contributes the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem, and opens up numerous avenues for further study of Polyamorous Scheduling.
Cite as

Leszek Gąsieniec, Benjamin Smith, and Sebastian Wild. Polyamorous Scheduling. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gasieniec_et_al:LIPIcs.FUN.2024.15,
  author =	{G\k{a}sieniec, Leszek and Smith, Benjamin and Wild, Sebastian},
  title =	{{Polyamorous Scheduling}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.15},
  URN =		{urn:nbn:de:0030-drops-199234},
  doi =		{10.4230/LIPIcs.FUN.2024.15},
  annote =	{Keywords: Periodic scheduling, Pinwheel scheduling, Edge-coloring, Chromatic index, Approximation algorithms, Hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.09261.12
Increasing Stability of Crew Schedules in Airlines

Authors: Leena Suhl, Viktor Dück, and Natalia Kliewer

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
In airline traffic disruptions occur frequently and cannot be totally avoided. They may lead to infeasible aircraft and crew schedules during the day of operations, due to absence of resources or violation of crew rules. The process of finding new schedules in such cases is called recovery or disruption management. The short-term recovery actions usually imply additional costs meaning that the total operational costs of a crew schedule can be significantly higher than the original planned costs. It is generally desirable to construct the schedule already in the planning phase in such a way that not just the planned costs, but the total operational costs are minimized. The goal is thus to construct schedules which remain feasible or can be recovered without high costs in cases of disturbances. This approach is generally called robust scheduling.
Cite as

Leena Suhl, Viktor Dück, and Natalia Kliewer. Increasing Stability of Crew Schedules in Airlines. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{suhl_et_al:DagSemProc.09261.12,
  author =	{Suhl, Leena and D\"{u}ck, Viktor and Kliewer, Natalia},
  title =	{{Increasing Stability of Crew Schedules in Airlines}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.12},
  URN =		{urn:nbn:de:0030-drops-21786},
  doi =		{10.4230/DagSemProc.09261.12},
  annote =	{Keywords: Robust planning, crew scheduling, airlines}
}
  • Refine by Author
  • 1 Dück, Viktor
  • 1 Gąsieniec, Leszek
  • 1 Kliewer, Natalia
  • 1 Smith, Benjamin
  • 1 Suhl, Leena
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 Chromatic index
  • 1 Edge-coloring
  • 1 Hardness of approximation
  • 1 Periodic scheduling
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2009
  • 1 2024

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