Fall 2017

Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations

Tuesday, September 12th, 2017 3:30 pm4:00 pm

Add to Calendar

In this talk, I will cover some recent progresses on approximating non-preemptive scheduling problems with the total weighted completion time objective, under different machine settings. For many such problems, we give approximation algorithms improving upon the previous state-of-art results that stood for 15 to 20 years. Surprisingly, the improvements are achieved via some natural time-indexed linear programming relaxations, that were not explicitly studied in the literature.