Document

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

Nash flows over time describe the behavior of selfish users eager to reach their destination as early as possible while traveling along the arcs of a network with capacities and transit times. Throughout the past decade, they have been thoroughly studied in single-source single-sink networks for the deterministic queuing model, which is of particular relevance and frequently used in the context of traffic and transport networks. In this setting there exist Nash flows over time that can be described by a sequence of static flows featuring special properties, so-called `thin flows with resetting'. This insight can also be used algorithmically to compute Nash flows over time. We present an extension of these results to networks with multiple sources and sinks which are much more relevant in practical applications. In particular, we come up with a subtle generalization of thin flows with resetting, which yields a compact description as well as an algorithmic approach for computing multi-terminal Nash flows over time.

Leon Sering and Martin Skutella. Multi-Source Multi-Sink Nash Flows over Time. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sering_et_al:OASIcs.ATMOS.2018.12, author = {Sering, Leon and Skutella, Martin}, title = {{Multi-Source Multi-Sink Nash Flows over Time}}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, pages = {12:1--12:20}, 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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.12}, URN = {urn:nbn:de:0030-drops-97176}, doi = {10.4230/OASIcs.ATMOS.2018.12}, annote = {Keywords: Network congestion, Nash equilibrium, dynamic routing game, deterministic queuing model} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Minimizing the sum of weighted completion times on m identical
parallel machines is one of the most important and classical
scheduling problems. For the stochastic variant where processing
times of jobs are random variables, Möhring, Schulz, and Uetz (1999) presented the first and still best known approximation result,
achieving, for arbitrarily many machines, performance
ratio 1+1/2(1+Delta), where Delta is an upper bound on the
squared coefficient of variation of the processing times. We prove
performance ratio 1+1/2(sqrt(2)-1)(1+Delta)
for the same
underlying algorithm---the Weighted Shortest Expected Processing
Time (WSEPT) rule. For the special case of deterministic scheduling
(i.e., Delta=0), our bound matches the tight performance
ratio 1/2(1+sqrt(2)) of this algorithm (WSPT rule), derived by
Kawaguchi and Kyan in a 1986 landmark paper. We present several
further improvements for WSEPT's performance ratio, one of them
relying on a carefully refined analysis of WSPT yielding, for every
fixed number of machines m, WSPT's exact performance ratio of
order 1/2(1+sqrt(2))-O(1/m^2).

Sven Jäger and Martin Skutella. Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jager_et_al:LIPIcs.STACS.2018.43, author = {J\"{a}ger, Sven and Skutella, Martin}, title = {{Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {43:1--43:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.43}, URN = {urn:nbn:de:0030-drops-85034}, doi = {10.4230/LIPIcs.STACS.2018.43}, annote = {Keywords: Stochastic Scheduling, Parallel Machines, Approximation Algorithm, List Scheduling, Weighted Shortest (Expected) Processing Time Rule} }

Document

**Published in:** Dagstuhl Reports, Volume 5, Issue 10 (2016)

Traffic assignment models are crucial for traffic planners to be able to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, etc. The starting point of the seminar was the observation that there is a trend in the transportation community (science as well as industry) to base such predictions on complex computer-based simulations that are capable of resolving many elements of a real transportation system. On the other hand, within the past few years, the theory of dynamic traffic assignments in terms of equilibrium existence and equilibrium computation has not matured to the point matching the model complexity inherent in simulations. In view of the above, this interdisciplinary seminar brought together leading scientists in the areas traffic simulations, algorithmic game theory and dynamic traffic assignment as well as people from industry with strong scientific background who identified possible ways to bridge the described gap.

José R. Correa, Tobias Harks, Kai Nagel, Britta Peis, and Martin Skutella. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412). In Dagstuhl Reports, Volume 5, Issue 10, pp. 19-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{correa_et_al:DagRep.5.10.19, author = {Correa, Jos\'{e} R. and Harks, Tobias and Nagel, Kai and Peis, Britta and Skutella, Martin}, title = {{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412)}}, pages = {19--34}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {5}, number = {10}, editor = {Correa, Jos\'{e} R. and Harks, Tobias and Nagel, Kai and Peis, Britta and Skutella, Martin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.10.19}, URN = {urn:nbn:de:0030-drops-56938}, doi = {10.4230/DagRep.5.10.19}, annote = {Keywords: Dynamic traffic equilibria, Complexity of equilibrium computation, Simulation, Dynamic network flow theory, Network optimization} }

Document

**Published in:** LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the sizes of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. Here, the processing time of job j on machine i is governed by random variable P_{ij} , and its realization becomes known only upon job completion. With w_j being the given weight of job j, we study the objective to minimize the expected total weighted completion time E[Sum w_j.C_j] , where C_j is the completion time of job j. By means of a novel time-indexed linear programming relaxation, we compute in polynomial time a scheduling policy with performance guarantee (3+D)/2+e. Here, e>0 is arbitrarily small, and D is an upper bound on the squared coefficient of variation of the processing times. When jobs also have individual release dates r_{ij}, our bound is (2+D)+e. We also show that the dependence of the performance guarantees on D is tight. Via D=0, currently best known bounds for deterministic scheduling on unrelated machines are contained as special case.

Martin Skutella, Maxim Sviridenko, and Marc Uetz. Stochastic Scheduling on Unrelated Machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 639-650, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{skutella_et_al:LIPIcs.STACS.2014.639, author = {Skutella, Martin and Sviridenko, Maxim and Uetz, Marc}, title = {{Stochastic Scheduling on Unrelated Machines}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {639--650}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.639}, URN = {urn:nbn:de:0030-drops-44946}, doi = {10.4230/LIPIcs.STACS.2014.639}, annote = {Keywords: Stochastic Scheduling, Unrelated Machines, Approximation Algorithm} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

We consider a real-time scheduling problem that occurs in the design
of software-based aircraft control. The goal is to distribute tasks
$ au_i=(c_i,p_i)$ on a minimum number of identical machines and to
compute offsets $a_i$ for the tasks such that no collision occurs. A
task $ au_i$ releases a job of running time $c_i$ at each time $a_i +
kcdot p_i, , k in mathbb{N}_0$ and a collision occurs if two jobs are
simultaneously active on the same machine.
We shed some light on the complexity and approximability landscape of this problem.
Although the problem cannot be approximated
within a factor of $n^{1-varepsilon}$ for any $varepsilon>0$, an interesting restriction
is much more tractable: If the periods are dividing (for each $i,j$ one has $p_i |
p_j$ or $p_j | p_i$), the problem allows for a better structured representation of solutions, which leads
to a 2-approximation. This result is tight, even asymptotically.

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{eisenbrand_et_al:DagSemProc.10071.13, author = {Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jose and Wiese, Andreas}, title = {{Scheduling periodic tasks in a hard real-time environment}}, booktitle = {Scheduling}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10071}, editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.13}, URN = {urn:nbn:de:0030-drops-25348}, doi = {10.4230/DagSemProc.10071.13}, annote = {Keywords: Real-Time Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm} }

Document

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

In general, combinatorial optimization problems are unstable: slight changes on the instance of a problem can render huge changes in the optimal solution. Thus, a natural question arises: Can we achieve stability if we only maintain approximate solutions?. In this talk I will first formalize these ideas, and then show some results on the parallel machine covering problem. In particular I will derive a robust PTAS, i.e., I will show how to construct a solution that is not only $(1-epsilon)$-approximate, but is also stable. That is, if the instance is changed by adding or removing a job, then we can construct a new near-optimal solution by only slightly modifying the previous one.

Martin Skutella and Jose Verschae. A Robust PTAS for the Parallel Machine Covering Problem. 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{skutella_et_al:DagSemProc.09261.4, author = {Skutella, Martin and Verschae, Jose}, title = {{A Robust PTAS for the Parallel Machine Covering Problem}}, 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.4}, URN = {urn:nbn:de:0030-drops-21609}, doi = {10.4230/DagSemProc.09261.4}, annote = {Keywords: Stability, approximation schemes, online algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Earliest arrival flows are motivated by applications related to
evacuation. Given a network with capacities and transit times on
the arcs, a subset of source nodes with supplies and a sink node,
the task is to send the given supplies from the sources to the sink
"as quickly as possible". The latter requirement is made more
precise by the earliest arrival property which requires that the
total amount of flow that has arrived at the sink is maximal for all
points in time simultaneously.
It is a classical result from the 1970s that, for the special case
of a single source node, earliest arrival flows do exist and can be
computed by essentially applying the Successive Shortest Path
Algorithm for min-cost flow computations. While it has previously
been observed that an earliest arrival flow still exists for
multiple sources, the problem of computing one efficiently has been
open. We present an exact algorithm for this problem whose running
time is strongly polynomial in the input plus output size of the
problem.

Nadine Baumann and Martin Skutella. Computing earliest arrival flows with multiple sources. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:DagSemProc.05361.4, author = {Baumann, Nadine and Skutella, Martin}, title = {{Computing earliest arrival flows with multiple sources}}, booktitle = {Algorithmic Aspects of Large and Complex Networks}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {5361}, editor = {Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.4}, URN = {urn:nbn:de:0030-drops-5672}, doi = {10.4230/DagSemProc.05361.4}, annote = {Keywords: Networks, flows over time, dynamic flows, earliest arrival, evacuation} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by~$\beta$ times the size of the arriving job. Our main result is a linear time `online approximation scheme', that is, a family of online algorithms with competitive ratio~$1+\epsilon$ and constant migration factor~$\beta(\epsilon)$, for any fixed~$\epsilon>0$. This result is of particular importance if considered in the context of sensitivity analysis: While a newly arriving job may force a complete change of the entire structure of an optimal schedule, only very limited `local' changes suffice to preserve near-optimal solutions. We believe that this concept will find wide application in its own right. We also present simple deterministic online algorithms with migration factors~$\beta=2$ and~$\beta=4/3$, respectively. Their competitive ratio~$3/2$ beats the lower bound on the performance of any online algorithm in the classical setting without migration. We also present improved algorithms and similar results for closely related problems. In particular, there is a short discussion of corresponding results for the objective to maximize the minimum load of a machine. The latter problem has an application for configuring storage servers that was the original motivation for this work.

Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online Scheduling with Bounded Migration. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{sanders_et_al:DagSemProc.05031.22, author = {Sanders, Peter and Sivadasan, Naveen and Skutella, Martin}, title = {{Online Scheduling with Bounded Migration}}, booktitle = {Algorithms for Optimization with Incomplete Information}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {5031}, editor = {Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.22}, URN = {urn:nbn:de:0030-drops-707}, doi = {10.4230/DagSemProc.05031.22}, annote = {Keywords: scheduling, sensitivity analysis, online algorithm} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail