TITLE: A Greedy Approximation Algorithm for Minimum-Gap Scheduling

Speaker: Marek Chrobak,UC Riverside

Time/Date:  Friday, Oct 26, 11-12
Location: Room 3301A

Abstract:

We consider scheduling unit-length jobs with release times and deadlines, where the
objective is to minimize the number of gaps in the schedule. This problem arises in minimizing
energy consumption of computing systems, with gaps in the schedule representing the periods
where the system can be powered down. Polynomial-time algorithms for this problem are known, yet 
they are rather inefficient, with the best algorithm running in time O(n^4) and requiring O(n^3) 
memory. We present a greedy algorithm that approximates the optimum solution within a factor of 
2 and show that our analysis is tight. Our algorithm runs in time O(n^2*logn) and needs only 
O(n) memory. In fact, the running time is O(n*g*logn), where g is the minimum number of gaps.

Joint work with Uriel Feige, Mohammad Taghi Hajiaghayi,	Sanjeev Khanna,	Fei Li, and Seffi Naor.