2020/04/02 by Shi Li, Li, Shi · 1 citation
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2004.01231
openalex publication_date 2020/04/02 · openalex created_date 2020/04/10 · openalex updated_date 2026/07/28
We study the classic problem of scheduling n precedence constrained unit-size jobs on m = O(1) machines so as to minimize the makespan. In a recent breakthrough, Levey and Rothvoss \citeLR16 developed a (1+ε)-approximation for the problem with running time exp(exp(O((m2)/(ε2)log2log n))), via the Sherali-Adams lift of the basic linear programming relaxation for the problem by exp(O((m2)/(ε2)log2log n)) levels. Garg \citeGarg18 recently improved the number of levels to log O(m2/ε2)n, and thus the running time to exp(log O(m2/ε2)n), which is quasi-polynomial for constant m and ε. In this paper we present an algorithm that achieves (1+ε)-approximation for the problem with running time nO((m4)/(ε3)log3log n), which is very close to a polynomial for constant m and ε. Unlike the algorithms of Levey-Rothvoss and Garg, which are based on linear-programming hierarchy, our algorithm is purely combinatorial. For this problem, we show that the conditioning operations on the lifted LP solution can be replaced by making guesses about the optimum schedule.