Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
2010 (English)In: STOC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON THEORY OF COMPUTING, NEW YORK: ASSOC COMPUTING MACHINERY , 2010, 745-754 p.Conference paper (Refereed)
Already in 1966, Graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. Till this date it has remained the best algorithm and whether it can or cannot be improved has become a major open problem in scheduling theory. We address this problem by establishing a quite surprising relation 'between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. More specifically, we prove that if the single machine problem is hard to approximate within a factor of 2 - epsilon then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of 2 - zeta, where zeta tends to 0 as epsilon tends to 0. Combining this with Bansal & Khot's recent hardness result for the single machine problem gives that it is NP-hard to improve upon the approximation ratio obtained by Graham, assuming a new variant of the unique games conjecture.
Place, publisher, year, edition, pages
NEW YORK: ASSOC COMPUTING MACHINERY , 2010. 745-754 p.
IdentifiersURN: urn:nbn:se:kth:diva-31635DOI: 10.1145/1806689.1806791ISI: 000286949900077ScopusID: 2-s2.0-77954728477ISBN: 978-1-60558-817-9OAI: oai:DiVA.org:kth-31635DiVA: diva2:405469
42nd ACM Symposium on Theory of Computing Cambridge, MA, JUN 06-08, 2010
QC 201103222011-03-222011-03-212011-03-22Bibliographically approved