Change search
ReferencesLink to record
Permanent link

Direct link
Conditional Hardness of Precedence Constrained Scheduling on Identical Machines
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
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)
Abstract [en]

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
National Category
Computer Science
URN: urn:nbn:se:kth:diva-31635DOI: 10.1145/1806689.1806791ISI: 000286949900077ScopusID: 2-s2.0-77954728477ISBN: 978-1-60558-817-9OAI: diva2:405469
42nd ACM Symposium on Theory of Computing Cambridge, MA, JUN 06-08, 2010
QC 20110322Available from: 2011-03-22 Created: 2011-03-21 Last updated: 2011-03-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Svensson, Ola
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link