Quasi-PTAS for scheduling with precedences using LP hierarchies

Shashwat Garg

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
9 Downloads (Pure)

Samenvatting

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 , polylog(n) rounds of Sherali-Adams hierarchy applied to a natural LP of the problem provides a (1+)-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 + )-approximation algorithm with a running time of nO(r)..

Originele taal-2Engels
Titel45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
RedacteurenIoannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, Donald Sannella
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's13
Volume107
ISBN van elektronische versie9783959770767
DOI's
StatusGepubliceerd - 1 jul 2018
Evenement45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Tsjechië
Duur: 9 jul 201813 jul 2018

Congres

Congres45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
LandTsjechië
StadPrague
Periode9/07/1813/07/18

Vingerafdruk Duik in de onderzoeksthema's van 'Quasi-PTAS for scheduling with precedences using LP hierarchies'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Garg, S. (2018). Quasi-PTAS for scheduling with precedences using LP hierarchies. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (editors), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (Vol. 107). [9063] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2018.59