MSc Seminar on March 8, 2018 in room Carre  2E

For a list of MSc seminars, click here.


For a list of seminars and conferences, click here.  

Operations Research seminar

Operations Research Seminar on January 30, 12.45-13.30

Speaker: Marc Uetz
Affiliation: UT-EWI-DMMP
Title: Greed is Good (for Scheduling under Uncertainty)
The talk addresses a classical problem in the area of scheduling, namely minimizing the total weighted completion time of non-preemptive jobs on a set of unrelated machines. Uncertainty enters the model by assuming that job processing times are stochastic. In order to obtain constant factor approximation algorithms for that problem, prior work required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. In contrast, we analyze a purely combinatorial, online algorithm. Maybe surprisingly, we show how to derive performance bounds for that algorithm that are of the same order of magnitude as those of earlier work, while our results are the first for an online setting. The analysis is based on dual fitting techniques.
Joint work with Varun Gupta (U Chicago), Ben Moseley (CMU), Qiaomin Xi (MIT).

For a list of Operations Research seminars, click here.