Optimization seminar

Modal title

Modal content

Spring Semester 2020

Date / Time

Speaker

Title

Location

24 February 2020
16:30-17:30

Dr. Jakub Tarnawski
Microsoft Research, Redmond, USA

Event Details

Optimization Seminar

Title	Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Speaker, Affiliation	Dr. Jakub Tarnawski, Microsoft Research, Redmond, USA
Date, Time	24 February 2020, 16:30-17:30
Location	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 March 2020
16:30-17:30

Dr. Nina Holden
Institute for Theoretical Studies, ETH Zürich, Switzerland

Event Details

Optimization Seminar

Title	Trace reconstruction for bit strings
Speaker, Affiliation	Dr. Nina Holden, Institute for Theoretical Studies, ETH Zürich, Switzerland
Date, Time	16 March 2020, 16:30-17:30
Location	HG G 19.1

Trace reconstruction for bit strings (CANCELLED)

HG G 19.1

23 March 2020
16:30-17:30

Prof. Dr. Andreas Galanis
University of Oxford, Oxford, UK

Event Details

Optimization Seminar

Title	Title T.B.A.
Speaker, Affiliation	Prof. Dr. Andreas Galanis, University of Oxford, Oxford, UK
Date, Time	23 March 2020, 16:30-17:30
Location	HG G 19.2

Title T.B.A. (CANCELLED)

HG G 19.2

30 March 2020
10:30-11:30

Matteo Tacchi
LAAS-CNRS, Toulouse, France

Event Details

Optimization Seminar

Title	Title T.B.A.
Speaker, Affiliation	Matteo Tacchi, LAAS-CNRS, Toulouse, France
Date, Time	30 March 2020, 10:30-11:30
Location	HG G 19.1

Title T.B.A. (CANCELLED)

HG G 19.1

6 April 2020
16:30-17:30

Antoine Maillard
Ecole Normale Supérieure Paris, France

Event Details

Optimization Seminar

Title	Title T.B.A.
Speaker, Affiliation	Antoine Maillard, Ecole Normale Supérieure Paris, France
Date, Time	6 April 2020, 16:30-17:30
Location	HG G 19.1

Title T.B.A. (CANCELLED)

HG G 19.1

27 April 2020
16:30-17:30

Dr. Daniel Dadush
Centrum Wiskunde & Informatica (CWI), Amsterdam, NL

Event Details

Optimization Seminar

Title	Title T.B.A.
Speaker, Affiliation	Dr. Daniel Dadush, Centrum Wiskunde & Informatica (CWI), Amsterdam, NL
Date, Time	27 April 2020, 16:30-17:30
Location	ML H 43

Title T.B.A. (CANCELLED)

ML H 43

4 May 2020
16:30-17:30

Dr. Manuel F. Aprile
Université Libre de Bruxelles, Bruxelles, B

Event Details

Optimization Seminar

Title	Title T.B.A.
Speaker, Affiliation	Dr. Manuel F. Aprile, Université Libre de Bruxelles, Bruxelles, B
Date, Time	4 May 2020, 16:30-17:30
Location	HG G 19.1

Title T.B.A. (CANCELLED)

HG G 19.1

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09