Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


Event Address*:

Berkeley, U.S.A.

Language:

English

Event Date*
(no longer used):

August,8 - August, 11, 1999

Organization:


Event Start Date:

21 October 2019

Event End Date:

21 October 2019

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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