On the approximability of an interval scheduling problem

Research output: Contribution to journalArticleAcademicpeer-review

97 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)215-227
Number of pages13
JournalJournal of Scheduling
Volume2
Issue number5
DOIs
Publication statusPublished - 1999
Externally publishedYes

Keywords

  • Approximability
  • Independent set
  • Interval scheduling

Fingerprint Dive into the research topics of 'On the approximability of an interval scheduling problem'. Together they form a unique fingerprint.

  • Cite this