2026-07-20T05:13:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9063 2024-03-06T10:43:16Z ddc:004 open_access

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies Garg, Shashwat Approximation algorithms hierarchies scheduling rounding techniques A central problem in scheduling is to schedule n unit size jobs with precedence constraints on m identical machines so as to minimize the makespan. For m=3, it is not even known if the problem is NP-hard and this is one of the last open problems from the book of Garey and Johnson. We show that for fixed m and epsilon, {polylog}(n) rounds of Sherali-Adams hierarchy applied to a natural LP of the problem provides a (1+epsilon)-approximation algorithm running in quasi-polynomial time. This improves over the recent result of Levey and Rothvoss, who used r=(log n)^{O(log log n)} rounds of Sherali-Adams in order to get a (1+epsilon)-approximation algorithm with a running time of n^O(r). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shashwat Garg 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.59 urn:nbn:de:0030-drops-90638 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.59 eng https://creativecommons.org/licenses/by/3.0/legalcode