On the approximability of an interval scheduling problem
Frits C. R. Spieksma · Journal of Scheduling · 1999
In this paper we consider a general interval scheduling problem. The problem is a natural generalization of finding a maximum independent set in an interval graph. We show that, unless 𝒫=𝒩𝒫, this maximization problem cannot be approximated in polynomial time within arbitrarily good precision. On the other hand, we present a simple greedy algorithm that delivers a solution with a value of at least 1/2 times the value of an optimal solution. Finally, we investigate the quality of an LP-relaxation of a formulation for the problem, by establishing an upper bound on the ratio between the value of the LP-relaxation and the value of an optimal solution. Copyright © 1999 John Wiley & Sons, Ltd.