TY - JOUR
T1 - On the approximability of an interval scheduling problem
AU - Spieksma, F.C.R.
PY - 1999
Y1 - 1999
N2 - 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 = NP, 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.
AB - 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 = NP, 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.
KW - Approximability
KW - Independent set
KW - Interval scheduling
UR - http://www.scopus.com/inward/record.url?scp=0000321137&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-Y
DO - 10.1002/(SICI)1099-1425(199909/10)2:5<215::AID-JOS27>3.0.CO;2-Y
M3 - Article
AN - SCOPUS:0000321137
VL - 2
SP - 215
EP - 227
JO - Journal of Scheduling
JF - Journal of Scheduling
SN - 1094-6136
IS - 5
ER -