English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  A linear time approximation scheme for the job shop scheduling problem

Solis-Oba, R., Jansen, K., & Sviridenko, M. (1999). A linear time approximation scheme for the job shop scheduling problem. In D. Hochbaum, K. Jansen, J. D. P. Rolim, & A. Sinclair (Eds.), 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) (pp. 177-188). Berlin: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3591-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3593-F
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Solis-Oba, Roberto1, Author           
Jansen, Klaus1, Author           
Sviridenko, Maxim, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021999
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518025
Other: Local-ID: C1256428004B93B8-86B6BC715FDC2E3CC12567D10053A40A-Solis-Oba1999f
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Berkeley, U.S.A.
Start-/End Date: 1999

Legal Case

show

Project information

show

Source 1

show
hide
Title: 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)
Source Genre: Proceedings
 Creator(s):
Hochbaum, Dorit, Editor
Jansen, Klaus1, Editor           
Rolim, José D. P., Editor
Sinclair, Alistair, Editor
Affiliations:
1 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 177 - 188 Identifier: ISBN: 3-540-66329-0

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1671 Sequence Number: - Start / End Page: - Identifier: -