TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenSven Jäger

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Sven Jäger

Lupe

Wissenschaftlicher Mitarbeiter

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-2

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Deutschland

E-Mail:
Tel.: +49 (0)30 314-21095
Fax: +49 (0)30 314-25191
Raum: MA 511
Sprechzeiten: Dienstag 17:00 Uhr. Bitte schicken Sie mir bis Dienstagmittag eine E-Mail, um den Zoom-Link zu erhalten.

Forschungsinteressen

  • Approximationsalgorithmen
  • Scheduling
  • Symmetrische Kettenzerlegungen

Lehre

Assistenzen
SS 2021
Computerorientierte Mathematik II (theoretische Hausaufgaben)
WS 2020/21
Introduction to Linear and Combinatorial Optimization (ADM I)
SS 2020
Discrete Optimization (ADM II)
WS 2019/20
Introduction to Linear and Combinatorial Optimization (ADM I)
SS 2019
Discrete Optimization (ADM II)
WS 2018/19
Introduction to Linear and Combinatorial Optimization (ADM I)
SS 2018
Computerorientierte Mathematik II (Programmieraufgaben)
WS 2017/18
Computerorientierte Mathematik I (Programmieraufgaben)
SS 2017
Computerorientierte Mathematik II (theoretische Hausaufgaben)
WS 2016/17
Computerorientierte Mathematik I (theoretische Hausaufgaben)

Lebenslauf

Seit Juli 2016
Wissenschaftlicher Mitarbeiter am Lehrstuhl von Martin Skutella, Technische Universität Berlin
2013 - 2016:
Masterstudium der Mathematik und der Angewandten Informatik an der Georg-August-Universität Göttingen
2010 - 2013:
Bachelor-Studium der Mathematik und der Angewandten Informatik an der Georg-August-Universität Göttingen
2010:
Abitur am Hainberg-Gymnasium Göttingen

Veröffentlichungen

Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling
Zitatschlüssel JaegerSkutella2018
Autor Jäger, Sven and Skutella, Martin
Buchtitel 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Seiten 43:1–43:14
Jahr 2018
ISBN 978-3-95977-062-0
ISSN 1868-8969
DOI 10.4230/LIPIcs.STACS.2018.43
Ort Caen
Adresse Dagstuhl, Germany
Jahrgang 96
Herausgeber Niedermeier, Rolf and Vallée, Brigitte
Verlag Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
Serie Leibniz International Proceedings in Informatics (LIPIcs)
Zusammenfassung 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+Δ), where Δ is an upper bound on the squared coefficient of variation of the processing times. We prove performance ratio 1+1/2(√2-1)(1+Δ) for the same underlying algorithm–-the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e., Δ=0), our bound matches the tight performance ratio 1/2(1+√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+√2)-O(1/m²).
Link zur Originalpublikation Download Bibtex Eintrag
Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling
Zitatschlüssel JaegerSkutella2018
Autor Jäger, Sven and Skutella, Martin
Buchtitel 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Seiten 43:1–43:14
Jahr 2018
ISBN 978-3-95977-062-0
ISSN 1868-8969
DOI 10.4230/LIPIcs.STACS.2018.43
Ort Caen
Adresse Dagstuhl, Germany
Jahrgang 96
Herausgeber Niedermeier, Rolf and Vallée, Brigitte
Verlag Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik
Serie Leibniz International Proceedings in Informatics (LIPIcs)
Zusammenfassung 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+Δ), where Δ is an upper bound on the squared coefficient of variation of the processing times. We prove performance ratio 1+1/2(√2-1)(1+Δ) for the same underlying algorithm–-the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e., Δ=0), our bound matches the tight performance ratio 1/2(1+√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+√2)-O(1/m²).
Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe