Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms

Shi Li

TL;DR

This paper moves us closer to a Polynomial Time Approximation Scheme (PTAS) for the classic problem of scheduling precedence-constrained jobs on a fixed number of machines. By replacing complex linear programming (LP) hierarchies with a clever "combinatorial guessing" framework, the author achieves a $(1+\epsilon)$-approximation with a running time that significantly improves upon previous quasi-polynomial results.

What Problem Does This Paper Address?

The paper tackles a fundamental challenge in scheduling theory: $P|prec, p_j=1|C_{max}$.

In plain English: you have $n$ jobs, each taking exactly one unit of time. You have $m$ identical machines. Crucially, there are "precedence constraints"—certain jobs must finish before others can start. Your goal is to minimize the makespan (the total time to finish everything).

When the number of machines $m$ is part of the input, the problem is notoriously hard to approximate. However, when $m$ is a small constant (like 3 or 4), researchers have long hunted for a PTAS—an algorithm that can get within a $(1+\epsilon)$ factor of the optimal solution in time that is polynomial in $n$ for any fixed $\epsilon$. Previous breakthroughs used the "Sherali-Adams" LP hierarchy, but these resulted in quasi-polynomial runtimes with heavy dependencies on $1/\epsilon$.

Methods

The author departs from the recent trend of using massive LP relaxations. Instead, the paper proposes a purely combinatorial algorithm based on a "guessing framework."

  1. Dyadic Interval Tree: The time horizon is divided into a tree of intervals (halving the time at each level). Jobs are assigned to "owning intervals" where they are expected to be processed.
  2. The Guessing Framework: Previous algorithms used "conditioning" on LP solutions (fixing a fractional variable to 1 and seeing what happens). This paper shows that you can instead "guess" binary information about the optimal schedule—specifically, whether a job in a long precedence chain falls into the left or right half of its current time interval.
  3. Recursive Decomposition: If a set of jobs in an interval has a long precedence chain, the algorithm picks a middle job, guesses its placement, and uses that to split the problem into independent sub-problems.
  4. Virtually-Valid Schedules: To handle the messy dependencies between jobs in different intervals, the author introduces "window constraints." These allow the algorithm to ignore some precedence constraints temporarily, creating a "virtually-valid" schedule that can later be converted into a true valid schedule by discarding only a small fraction of jobs.

Datasets

Not discussed in the paper. As a theoretical computer science paper, the results are established through mathematical proofs and worst-case complexity analysis rather than empirical testing on datasets.

Key Insights and Ideas

  • Binary Guesses are Cheap: In the LP hierarchy framework, each "conditioning" operation typically incurs a multiplicative factor of $poly(n)$ in the runtime. In the guessing framework, many guesses are binary (Left vs. Right), contributing only a factor of 2. This "saves" a $\log n$ factor in the exponent of the running time.
  • Flexibility: Guessing is more flexible than LP conditioning. You can guess any property of the optimal schedule that can be described in a few bits, whereas LP conditioning is restricted to the variables defined in the base relaxation.
  • Overcoming the Recursive Barrier: Previous recursive LP approaches hit a runtime barrier of $n^{\Omega(\log n / \log \log n)}$. By using a more efficient way to pass information down the recursion (guessing critical intervals rather than the whole tree), this paper pushes the runtime down to nearly polynomial.
  • Single vs. Double Exponential: The algorithm achieves a "single exponential" dependence on $1/\epsilon$, whereas the previous best result by Garg (2018) had a "double exponential" dependence.

Key Results

  • Approximation Guarantee: A $(1+\epsilon)$-approximation for any $\epsilon > 0$.
  • Improved Runtime: The algorithm runs in $n^{O(\frac{m^4}{\epsilon^3} \log^3 \log n)}$ time.
  • Significance: This is "quasi-quasi-polynomial"—it is much closer to a true PTAS ($n^{f(m, \epsilon)}$) than previous results. It effectively removes one of the $\log n$ factors from the exponent that plagued earlier hierarchy-based methods.

Limitations and Future Work

  • Not quite a PTAS: The presence of the $\log^3 \log n$ term in the exponent means the runtime is still technically quasi-polynomial, though barely so. A true PTAS would require removing this term entirely.
  • The "Discarding" Loss: The algorithm works by finding a schedule for most jobs and then inserting the "discarded" ones back in, which adds to the makespan. The author suggests that a more refined analysis of these discarded jobs is the most likely path toward achieving a true PTAS.
  • Combinatorial vs. LP: While this paper shows the power of combinatorial methods, the author notes it would be interesting to see if the Sherali-Adams hierarchy could be tuned to achieve similar efficiency.

Summary updated

Abstract

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 [11] developed a (1 +∊)-approximation for the problem with running time , via the Sherali-Adams lift of the basic linear programming relaxation for the problem by levels. Garg [6] recently improved the number of levels to , and thus the running time to , 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).
BibTeX
@inproceedings{li2021towards,
  author = {Shi Li},
  title = {{Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=0wLWl7ialH},
}
Figure