Abstract
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.