Approximating an interval scheduling problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationApproximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings
Place of PublicationBerlin
PublisherSpringer
Pages169-180
Number of pages12
ISBN (Electronic)978-3-540-69067-2
ISBN (Print)978-3-540-64736-2
DOIs
Publication statusPublished - 1998
Externally publishedYes
EventInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998) - Aalborg, Denmark
Duration: 18 Jul 199819 Jul 1998

Publication series

NameLecture Notes in Computer Science
Volume1444
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998)
Abbreviated titleAPPROX 1998
CountryDenmark
CityAalborg
Period18/07/9819/07/98

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

Cite this