George Mason University
George Mason University Mason
George Mason University

A Greedy Approximation Algorithm for Minimum-Gap Scheduling

by Fei Li

Publication Details MORE LESS

  • Published Date: July 27, 2016
  • Volume/Issue: Vol. 20 Issue 3
  • Publisher: Springer
  • Publication: Journal of Scheduling
  • ISSN: 1099-1425


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)logn) and needs only O(n) memory. In fact, the running time is O(n((g^*)+1)logn), where g^* is the minimum number of gaps.

Other Contributors

Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khann, and Seffi Naor