A \((2 + \varepsilon)\)-approximation algorithm for the general scheduling problem in quasipolynomial time

We study the general scheduling problem (GSP) which generalizes and unifies several well-studied preemptive single-machine scheduling problems, such as weighted flow time, weighted sum of completion time, and minimizing the total weight of tardy jobs. We are given a set of jobs with their processing times and release times and seek to compute a (possibly preemptive) schedule for them on one machine. Each job incurs a cost that depends on its completion time in the computed schedule, as given by a separate job-dependent cost function for each job, and our objective is to minimize the total resulting cost of all jobs. The best known result for GSP is a polynomial time \(O(\log \log P)\)-approximation algorithm [Bansal and Pruhs, FOCS 2010, SICOMP 2014].