Document Open Access Logo

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies

Author Shashwat Garg

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.59.pdf
  • Filesize: 467 kB
  • 13 pages

Document Identifiers

Author Details

Shashwat Garg
  • Eindhoven University of Technology, Netherlands

Funding

  • Garg, Shashwat: Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 022.005.025.

Cite As Get BibTex

Shashwat Garg. Quasi-PTAS for Scheduling with Precedences using LP Hierarchies. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.59

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Approximation algorithms
  • hierarchies
  • scheduling
  • rounding techniques

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nikhil Bansal and Subhash Khot. Optimal long code test with one free bit. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 453-462. IEEE, 2009. Google Scholar
  2. Eden Chlamtac and Madhur Tulsiani. Convex relaxations and integrality gaps. In Handbook on semidefinite, conic and polynomial optimization, pages 139-169. Springer, 2012. Google Scholar
  3. Devdatta Gangal and Abhiram Ranade. Precedence constrained scheduling in (2- 7/3p+ 1) optimal. Journal of Computer and System Sciences, 74(7):1139-1146, 2008. Google Scholar
  4. Michael R Garey. Ds johnson computers and intractability. A Guide to the Theory of NP-Completeness, 1979. Google Scholar
  5. Ronald L Graham. Bounds for certain multiprocessing anomalies. Bell Labs Technical Journal, 45(9):1563-1581, 1966. Google Scholar
  6. Shui Lam and Ravi Sethi. Worst case analysis of two scheduling algorithms. SIAM Journal on Computing, 6(3):518-536, 1977. Google Scholar
  7. Monique Laurent. A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming. Mathematics of Operations Research, 28(3):470-496, 2003. Google Scholar
  8. Jan Karel Lenstra and AHG Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26(1):22-35, 1978. Google Scholar
  9. Elaine Levey and Thomas Rothvoss. A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 168-177. ACM, 2016. URL: http://dl.acm.org/citation.cfm?id=2897518, URL: http://dx.doi.org/10.1145/2897518.2897532.
  10. Thomas Rothvoß. The lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP, pages 1-25, 2013. Google Scholar
  11. Petra Schuurman and Gerhard J Woeginger. Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling, 2(5):203-213, 1999. Google Scholar
  12. Hanif D Sherali and Warren P Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, 3(3):411-430, 1990. Google Scholar
  13. Ola Svensson. Conditional hardness of precedence constrained scheduling on identical machines. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 745-754. ACM, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact