Quasi-PTAS for scheduling with precedences using LP hierarchies

Shashwat Garg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
14 Downloads (Pure)

Abstract

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)..

Original languageEnglish
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsIoannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, Donald Sannella
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages13
Volume107
ISBN (Electronic)9783959770767
DOIs
Publication statusPublished - 1 Jul 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: 9 Jul 201813 Jul 2018

Conference

Conference45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
CountryCzech Republic
CityPrague
Period9/07/1813/07/18

Keywords

  • Approximation algorithms
  • Hierarchies
  • Rounding techniques
  • Scheduling

Fingerprint Dive into the research topics of 'Quasi-PTAS for scheduling with precedences using LP hierarchies'. Together they form a unique fingerprint.

Cite this