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.
Prof. Naveen Garg is a Professor in the Computer Science and Engineering Department at IIT Delhi. He started at this department as an undergraduate student in 1987, completed a Ph.d. in 1994 and joined as an Assistant Professor in 1997. He was a postdoc and a member of the technical staff at MPI-Informatik, Saarbruecken from 1994 to 1997. He is a co-director of the Indo-German Max-Planck Center for Computer Science (IMPECS). He is also the current occupant of the Amar S. Gupta Chair for Decision Sciences at IIT Delhi.