On the approximability of an interval scheduling problem

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 P = N P, 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 ½ 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.