Loading...
Please wait, while we are loading the content...
Similar Documents
Computing near-optimal schedules
| Content Provider | Semantic Scholar |
|---|---|
| Author | Lenstra, Jan Karel Shmoys, David B. |
| Copyright Year | 1995 |
| Abstract | We survey a number ofresults on computing near-optimal solutions for .N'P'-hard scheduling problems. For many .N'P'-hard optimization problems there are polynomial-time approximation algorithms for finding solutions that are provably quite close to the optimum, whereas for others no such algorithm is known. We concentrate on results that state that certain performance guarantees are unlikely to be attained, in the sense that if there is such a good algorithm, then P'= N P. In particular, we survey results for multiprocessor scheduling and shop scheduling problems. |
| Starting Page | 1 |
| Ending Page | 14 |
| Page Count | 14 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/2249029/427425.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
