Primal-Dual Algorithms in Scheduling


Naveen Garg


Indian Institute of Technology, Delhi
Department of Computer Science
and Engineering
Hauz Khas
New Delhi 110016


Tuesday, 17 November 2015, 16:00 to 17:00


  • A-212 (STCS Seminar Room)


Abstract: Recent years have seen application of Linear programming techniques to solve problems in scheduling. One technique that has been applied very effectively to both online and offline scheduling problems is the Primal-Dual method. In this talk I will take two examples from our own research to illustrate some of the key ideas. The problems I will consider are:

- the online problem of minimizing flow time on unrelated machines

- the offline problem of minimizing weighted flow time on a single machine.

The talk will assume only basic familiarity with linear programming and duality.