首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Quasi-PTAS for Scheduling with Precedences using LP Hierarchies
  • 作者:Shashwat Garg
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:107
  • 页码:59:1-59:13
  • DOI:10.4230/LIPIcs.ICALP.2018.59
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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).
  • 关键词:Approximation algorithms; hierarchies; scheduling; rounding techniques
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有