MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Solis-Oba, Roberto
Jansen, Klaus
Sviridenko, Maxim
dblp
dblp
dblp
Editor(s):
Hochbaum, Dorit
Jansen, Klaus
Rolim, José D. P.
Sinclair, Alistair
dblp
dblp
dblp
dblp
BibTeX cite key*:
Solis-Oba1999f
Title, Booktitle
Title*:
A linear time approximation scheme for the job shop scheduling problem
Booktitle*:
Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Berkeley, U.S.A.
Language:
English
Event Date*
(no longer used):
August,8 - August, 11, 1999
Organization:
Event Start Date:
29 November 2020
Event End Date:
29 November 2020
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1671
Number:
Month:
August
Pages:
177-188
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
3-540-66329-0
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We study the preemptive and non-preemptive versions of the job shop scheduling pr
oblem when the number of machines and the number of operations per job are fixed.
We present linear time approximation schemes for both problems. These algorithms
are the best possible for such problems in two regards: they achieve the best po
ssible performance ratio since both problems are known to be strongly NP-hard; an
d they have optimum asymptotic time complexity.
Keywords:
Approximation algorithms, job shop scheduling
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Solis-Oba1999f,
AUTHOR = {Solis-Oba, Roberto and Jansen, Klaus and Sviridenko, Maxim},
EDITOR = {Hochbaum, Dorit and Jansen, Klaus and Rolim, Jos{\'e} D. P. and Sinclair, Alistair},
TITLE = {A linear time approximation scheme for the job shop scheduling problem},
BOOKTITLE = {Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX-99)},
PUBLISHER = {Springer},
YEAR = {1999},
VOLUME = {1671},
PAGES = {177--188},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Berkeley, U.S.A.},
MONTH = {August},
ISBN = {3-540-66329-0},
}


Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Roberto Solis-Oba
Created
08/18/1999 05:13:34 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Roberto Solis-Oba

Edit Dates
07.04.2000 09:25:20
29.03.2000 17:03:05
08/18/99 05:13:35 PM