Page Content
Sven Jäger
- © privat
Research assistant
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
Germany
E-Mail: jaeger #at# math.tu-berlin.de
Tel.: +49 (0)30 314-21095
Fax: +49 (0)30 314-25191
Room: MA 511
Consultation hours: Tuesday 5:00 pm. Please send me an email before Tuesday noon in order to get the zoom link.
Teaching
| Summer 2021 | Computerorientierte Mathematik II (theoretical exercises) |
| Winter 2020/21 | Introduction to Linear and Combinatorial Optimization (ADM I) |
| Summer 2020 | Discrete Optimization (ADM II) |
| Winter 2019/20 | Introduction to Linear and Combinatorial Optimization (ADM I) |
| Summer 2019 | Discrete Optimization (ADM II) |
| Winter 2018/19 | Introduction to Linear and Combinatorial Optimization (ADM I) |
| Summer 2018 | Computerorientierte Mathematik II (programming exercises) |
| Winter 2017/18 | Computerorientierte Mathematik I (programming exercises) |
| Summer 2017 | Computerorientierte Mathematik II (theoretical exercises) |
| Winter 2016/17 | Computerorientierte Mathematik I (theoretical exercises) |
Curriculum Vitae
| Since July 2016 | Doctoral student with Martin Skutella, Technische Universität Berlin |
| 2013 - 2016: | Master studies in Mathematics and in Applied Computer Science at Georg-August-Universität Göttingen, Germany. |
| 2010 - 2013: | Bachelor studies in Mathematics and in Applied Computer Science at Georg-August-Universität Göttingen, Germany. |
| 2010: | Abitur at Hainberg-Gymnasium Göttingen |
Publications
| Citation key | JaegerSkutella2018 |
|---|---|
| Author | Jäger, Sven and Skutella, Martin |
| Title of Book | 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
| Pages | 43:1–43:14 |
| Year | 2018 |
| ISBN | 978-3-95977-062-0 |
| ISSN | 1868-8969 |
| DOI | 10.4230/LIPIcs.STACS.2018.43 |
| Location | Caen |
| Address | Dagstuhl, Germany |
| Volume | 96 |
| Editor | Niedermeier, Rolf and Vallée, Brigitte |
| Publisher | Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |
| Series | Leibniz International Proceedings in Informatics (LIPIcs) |
| Abstract | 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²). |
| Citation key | JaegerSkutella2018 |
|---|---|
| Author | Jäger, Sven and Skutella, Martin |
| Title of Book | 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) |
| Pages | 43:1–43:14 |
| Year | 2018 |
| ISBN | 978-3-95977-062-0 |
| ISSN | 1868-8969 |
| DOI | 10.4230/LIPIcs.STACS.2018.43 |
| Location | Caen |
| Address | Dagstuhl, Germany |
| Volume | 96 |
| Editor | Niedermeier, Rolf and Vallée, Brigitte |
| Publisher | Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |
| Series | Leibniz International Proceedings in Informatics (LIPIcs) |
| Abstract | 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²). |
Talks
- Approximating Total Weighted Completion Time on Identical Parallel Machines with Precedence Constraints and Release Dates MAPSP 2019 PDF, 292 KB
- Generalizing the Kawaguchi-Kyan Bound to Stochastic Parallel Machine Scheduling COW 2018, STACS 2018, ISMP 2018, BMS-BGSMath Junior Meeting 2019, FRICO 2019 PDF, 232 KB
- Gray codes and symmetric chains ICALP 2018 PDF, 381 KB
- On orthogonal symmetric chain decompositions EUROCOMB 2019 PDF, 449 KB
- Scheduling Stochastic Jobs with Release Dates on a Single Machine Dagstuhl Seminar Scheduling 2020 PDF, 457 KB
Zusatzinformationen / Extras
Quick Access:
Schnellnavigation zur Seite über Nummerneingabe
Auxiliary Functions
- Font size:
This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.