Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms

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 [10] developed a (1 + )-approximation for the problem with running time exp exp O m 2 2 log 2 log n , via the Sherali-Adams lift of the basic linear programming relaxation for the problem by exp O m 2 2 log 2 log n levels. Garg [5] recently improved the number of levels to log O(m 2 / 2 ) n, and thus the running time to exp log O(m 2 / 2 ) n , which is quasi-polynomial for constant m and .

In this paper we present a (1 + )-approximation algorithm for the problem with running time

, which is very close to a polynomial for constant m and . Unlike the algorithms of Levey-Rothvoss and Garg, which are based on the linear-programming hierarchy, our algorithm is purely combinatorial. We show that the conditioning operations on the lifted LP solution can be replaced by making guesses about the optimum schedule.

Compared to the LP hierarchy framework, our guessing framework has two advantages, both playing important roles in deriving the improved running time. First, we can guess any information about the optimum schedule, as long as it can be described using a few bits, while in the conditioning framework, we can only condition on the variables in the basic LP. Second, the guessing framework can save a factor of log n in the exponent of running time. Roughly speaking, most of the time, the information we try to guess is binary and thus each nested guess only contributes to a multiplicative factor of 2 in the running time. In contrast, each conditioning operation in a sequence incurs a multiplicative factor of poly(n).