Hardness of Approximating Flow and Job Shop Scheduling Problems

We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known inapproximability result says that it is NP-hard to approximate job shops within a factor less than 5/4. Closing this big approximability gap is a well-known and long-standing open problem.


Published in:
Journal Of The Acm, 58, -
Year:
2011
Keywords:
Laboratories:




 Record created 2011-12-16, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)