@inproceedings{5394692205754c70b68f79be8055f0b7,

title = "Approximating an interval scheduling problem",

abstract = "In this paper we consider a general interval scheduling problem. 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.",

author = "F.C.R. Spieksma",

year = "1998",

doi = "10.1007/BFb0053973",

language = "English",

isbn = "978-3-540-64736-2",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "169--180",

booktitle = "Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings",

address = "Germany",

note = "International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998), APPROX 1998 ; Conference date: 18-07-1998 Through 19-07-1998",

}