LP Rounding and Combinatorial Algorithms for Minimizing Active and Busy Time

Jessica Chang, Samir Khuller, Koyel Mukherjee

We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline and required processing le…