Approximating an interval scheduling problem

F.C.R. Spieksma

doi:10.1007/BFb0053973

Approximating an interval scheduling problem

F.C.R. Spieksma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

14 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 language	English
Title of host publication	Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings
Place of Publication	Berlin
Publisher	Springer
Pages	169-180
Number of pages	12
ISBN (Electronic)	978-3-540-69067-2
ISBN (Print)	978-3-540-64736-2
DOIs	https://doi.org/10.1007/BFb0053973
Publication status	Published - 1998
Externally published	Yes
Event	International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998) - Aalborg, Denmark Duration: 18 Jul 1998 → 19 Jul 1998

Publication series

Name	Lecture Notes in Computer Science
Volume	1444
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998)
Abbreviated title	APPROX 1998
Country/Territory	Denmark
City	Aalborg
Period	18/07/98 → 19/07/98

Access to Document

10.1007/BFb0053973

Cite this

@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",

}

Spieksma, FCR 1998, Approximating an interval scheduling problem. in Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. Lecture Notes in Computer Science , vol. 1444, Springer, Berlin, pp. 169-180, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998), Aalborg, Denmark, 18/07/98. https://doi.org/10.1007/BFb0053973

Approximating an interval scheduling problem. / Spieksma, F.C.R.
Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. Berlin: Springer, 1998. p. 169-180 (Lecture Notes in Computer Science ; Vol. 1444).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximating an interval scheduling problem

AU - Spieksma, F.C.R.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958953408&partnerID=8YFLogxK

U2 - 10.1007/BFb0053973

DO - 10.1007/BFb0053973

M3 - Conference contribution

AN - SCOPUS:84958953408

SN - 978-3-540-64736-2

T3 - Lecture Notes in Computer Science

SP - 169

EP - 180

BT - Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings

PB - Springer

CY - Berlin

T2 - International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 1998)

Y2 - 18 July 1998 through 19 July 1998

ER -

Approximating an interval scheduling problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this