A greedy approximation algorithm for minimum-gap scheduling

Marek Chrobak (), Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li and Seffi Naor
Additional contact information
Marek Chrobak: University of California
Uriel Feige: The Weizmann Institute
Mohammad Taghi Hajiaghayi: University of Maryland
Sanjeev Khanna: University of Pennsylvania
Fei Li: George Mason University
Seffi Naor: Technion

Journal of Scheduling, 2017, vol. 20, issue 3, No 5, 279-292

Abstract: 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)$$ O ( n 4 ) and requiring $$O(n^3)$$ 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)$$ O ( n 2 log n ) and needs only O(n) memory. In fact, the running time is $$O(n (g^*+1)\log n)$$ O ( n ( g ∗ + 1 ) log n ) , where $$g^*$$ g ∗ is the minimum number of gaps.

Keywords: Scheduling; Approximation algorithms; Greedy algorithms (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0492-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:3:d:10.1007_s10951-016-0492-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0492-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().