A greedy approximation algorithm for minimum-gap scheduling |
| |
| Authors: | Marek Chrobak Uriel Feige Mohammad Taghi Hajiaghayi Sanjeev Khanna Fei Li Seffi Naor |
| |
| Affiliation: | 1.Department of Computer Science and Engineering,University of California,Riverside,USA;2.Department of Computer Science and Applied Mathematics,The Weizmann Institute,Rehovot,Israel;3.Computer Science Department,University of Maryland,College Park,USA;4.Department of Computer and Information Science,University of Pennsylvania,Philadelphia,USA;5.Department of Computer Science,George Mason University,Fairfax,USA;6.Computer Science Department,Technion,Haifa,Israel |
| |
| Abstract: | We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. 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 \log n)\) and needs only O(n) memory. In fact, the running time is \(O(n (g^*+1)\log n)\), where \(g^*\) is the minimum number of gaps. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
