Tata Institute of Fundamental Research
Primal-Dual Algorithms in Scheduling
STCS Colloquium
Speaker:
Naveen Garg (Indian Institute of Technology, Delhi
Department of Computer Science
and Engineering
Hauz Khas
New Delhi 110016)
Organiser:
Umang Bhaskar
Date:
Tuesday, 17 Nov 2015, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Naveen Garg (Indian Institute of Technology, Delhi Department of Computer Science and Engineering Hauz Khas New Delhi 110016) |
| Organiser: | Umang Bhaskar |
| Date: | Tuesday, 17 Nov 2015, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
- 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.