Algorithms for Minimum-Gap Scheduling
- Speaker: Dr. Fei Li
- George Mason University
- Date: Friday, Feburary 27, 2015
- Time: 1:00pm - 2:00pm
- Location: Room 325 (NVC)
We consider scheduling of jobs with release times and deadlines to minimize the number of gaps in the schedule. The known algorithm is with running time O(n^5). When the jobs are with unit-length, the best algorithm for this problem runs in time O(n^4) and requires O(n^3) memory. A simple greedy algorithm approximates the optimum solution within a factor of 2. We show that the analysis is tight. This algorithm runs in time O(n^2 log n) and needs only O(n) memory. In fact, the running time is O(n g* log n), where g* is the minimum number of gaps.
Dr. Fei Li is an associate professor of Computer Science Department at George Mason University. Fei Li received his B.S. degree in Computer Science from Jilin University, Changchun, China, in 1997, his M.S., M.Phil., and Ph.D. degrees in Computer Science from Columbia University, New York, NY, in 2002, 2007, and 2008, respectively. Dr. Li's research interests include energy-aware scheduling algorithms, online and approximation algorithm design and analysis, combinatorial optimization, and applied algorithms for computing systems and networking. He has been on the editorial board of International Journal of Operations Research and Information Systems since 2008.