Quasi-PTAS for scheduling with precedences using LP hierarchies

Shashwat Garg

doi:10.4230/LIPIcs.ICALP.2018.59

Quasi-PTAS for scheduling with precedences using LP hierarchies

Shashwat Garg

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

53 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 n^O(r^)..

Original language	English
Title of host publication	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Editors	Ioannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, Donald Sannella
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	13
Volume	107
ISBN (Electronic)	9783959770767
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2018.59
Publication status	Published - 1 Jul 2018
Event	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic Duration: 9 Jul 2018 → 13 Jul 2018

Conference

Conference	45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/Territory	Czech Republic
City	Prague
Period	9/07/18 → 13/07/18

Keywords

Approximation algorithms
Hierarchies
Rounding techniques
Scheduling

Access to Document

10.4230/LIPIcs.ICALP.2018.59

Publishers VersionFinal published version, 467 KBLicence: CC BY

Cite this

@inproceedings{df20b4de947d485684566b2964890de4,

title = "Quasi-PTAS for scheduling with precedences using LP hierarchies",

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

keywords = "Approximation algorithms, Hierarchies, Rounding techniques, Scheduling",

author = "Shashwat Garg",

year = "2018",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.ICALP.2018.59",

language = "English",

volume = "107",

editor = "Ioannis Chatzigiannakis and Christos Kaklamanis and Daniel Marx and Donald Sannella",

booktitle = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

note = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 ; Conference date: 09-07-2018 Through 13-07-2018",

}

Garg, S 2018, Quasi-PTAS for scheduling with precedences using LP hierarchies. in I Chatzigiannakis, C Kaklamanis, D Marx & D Sannella (eds), 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. vol. 107, 9063, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9/07/18. https://doi.org/10.4230/LIPIcs.ICALP.2018.59

Quasi-PTAS for scheduling with precedences using LP hierarchies. / Garg, Shashwat.
45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. ed. / Ioannis Chatzigiannakis; Christos Kaklamanis; Daniel Marx; Donald Sannella. Vol. 107 Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 9063.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Quasi-PTAS for scheduling with precedences using LP hierarchies

AU - Garg, Shashwat

PY - 2018/7/1

Y1 - 2018/7/1

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

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

KW - Approximation algorithms

KW - Hierarchies

KW - Rounding techniques

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85049778770&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.59

DO - 10.4230/LIPIcs.ICALP.2018.59

M3 - Conference contribution

AN - SCOPUS:85049778770

VL - 107

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Chatzigiannakis, Ioannis

A2 - Kaklamanis, Christos

A2 - Marx, Daniel

A2 - Sannella, Donald

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Y2 - 9 July 2018 through 13 July 2018

ER -

Quasi-PTAS for scheduling with precedences using LP hierarchies

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this