Loading...
Please wait, while we are loading the content...
Similar Documents
Better Approximation Guarantees for Job-Shop Scheduling (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Goldberg, Leslie Ann Paterson, Mike Srinivasan, Aravind Sweedyk, Elizabeth |
| Abstract | Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein & Wein presented the rst polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work, and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). We also present NC algorithms with improved approximation guarantees for some NP-hard special cases. |
| File Format | |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Approximation Guarantee Job-shop Scheduling Rst Polynomial-time Approximation Algorithm Classical Np-hard Problem Np-hard Special Case Present Improvement Improved Approximation Guarantee Preemptive Case Stein Wein Important Np-hard Special Case Present Nc Algorithm |
| Content Type | Text |