Departement Mathematik

Optimization seminar

×

Modal title

Modal content

Frühjahrssemester 2020

Datum / Zeit Referent:in Titel Ort
24. Februar 2020
16:30-17:30 		Dr. Jakub Tarnawski
Microsoft Research, Redmond, USA
Details

Optimization Seminar

Titel Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Referent:in, Affiliation Dr. Jakub Tarnawski, Microsoft Research, Redmond, USA
Datum, Zeit 24. Februar 2020, 16:30-17:30
Ort HG G 19.1
Abstract We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact approximability of the problem when the number of machines is a constant is a well-known question in scheduling theory. Indeed, an outstanding open problem from the classic book of Garey and Johnson asks whether this problem is NP-hard even in the case of 3 machines and unit-length jobs. In a recent breakthrough, Levey and Rothvoss gave a (1 + eps)- approximation algorithm, which runs in nearly quasi-polynomial time, for the case when job have unit lengths. However, a substantially more difficult case where jobs have arbitrary processing lengths has remained open. We make progress on this more general problem. We show that there exists a (1 + eps)-approximation algorithm (with similar running time as that of Levey and Rothvoss) for the non-migratory setting: when every job has to be scheduled entirely on a single machine, but within a machine the job need not be scheduled during consecutive time steps. Further, we also show that our algorithmic framework generalizes to another classic scenario where, along with the precedence constraints, the jobs also have communication delay constraints. Both of these fundamental problems are highly relevant to the practice of datacenter scheduling. Joint work with Janardhan Kulkarni, Shi Li and Minwei Ye.
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraintsread_more
HG G 19.1
16. März 2020
16:30-17:30 		Dr. Nina Holden
Institute for Theoretical Studies, ETH Zürich, Switzerland
Details

Optimization Seminar

Titel Trace reconstruction for bit strings
Referent:in, Affiliation Dr. Nina Holden, Institute for Theoretical Studies, ETH Zürich, Switzerland
Datum, Zeit 16. März 2020, 16:30-17:30
Ort HG G 19.1
Trace reconstruction for bit strings (ABGESAGT)
HG G 19.1
23. März 2020
16:30-17:30 		Prof. Dr. Andreas Galanis
University of Oxford, Oxford, UK
Details

Optimization Seminar

Titel Title T.B.A.
Referent:in, Affiliation Prof. Dr. Andreas Galanis, University of Oxford, Oxford, UK
Datum, Zeit 23. März 2020, 16:30-17:30
Ort HG G 19.2
Title T.B.A. (ABGESAGT)
HG G 19.2
30. März 2020
10:30-11:30 		Matteo Tacchi
LAAS-CNRS, Toulouse, France
Details

Optimization Seminar

Titel Title T.B.A.
Referent:in, Affiliation Matteo Tacchi, LAAS-CNRS, Toulouse, France
Datum, Zeit 30. März 2020, 10:30-11:30
Ort HG G 19.1
Title T.B.A. (ABGESAGT)
HG G 19.1
6. April 2020
16:30-17:30 		Antoine Maillard
Ecole Normale Supérieure Paris, France
Details

Optimization Seminar

Titel Title T.B.A.
Referent:in, Affiliation Antoine Maillard, Ecole Normale Supérieure Paris, France
Datum, Zeit 6. April 2020, 16:30-17:30
Ort HG G 19.1
Title T.B.A. (ABGESAGT)
HG G 19.1
27. April 2020
16:30-17:30 		Dr. Daniel Dadush
Centrum Wiskunde & Informatica (CWI), Amsterdam, NL
Details

Optimization Seminar

Titel Title T.B.A.
Referent:in, Affiliation Dr. Daniel Dadush, Centrum Wiskunde & Informatica (CWI), Amsterdam, NL
Datum, Zeit 27. April 2020, 16:30-17:30
Ort ML H 43
Title T.B.A. (ABGESAGT)
ML H 43
4. Mai 2020
16:30-17:30 		Dr. Manuel F. Aprile
Université Libre de Bruxelles, Bruxelles, B
Details

Optimization Seminar

Titel Title T.B.A.
Referent:in, Affiliation Dr. Manuel F. Aprile, Université Libre de Bruxelles, Bruxelles, B
Datum, Zeit 4. Mai 2020, 16:30-17:30
Ort HG G 19.1
Title T.B.A. (ABGESAGT)
HG G 19.1

Hinweise: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archiv: FS 22 FS 20 HS 19 FS 19 HS 18 FS 18 HS 17 FS 17 HS 16 FS 16 HS 15 FS 15 HS 14 FS 14 HS 13 FS 13 HS 12 FS 12 HS 11 FS 11 HS 10 FS 10 HS 09

JavaScript wurde auf Ihrem Browser deaktiviert