Nicolás Stier-Moses

A Note on the Precedence-Constrained Class Sequencing Problem

Coauthor(s): José Correa, Samuel Fiorini.


Adobe Acrobat PDF


We give a short proof of a result of Tovey ["Non-approximability of precedence-constrained sequencing to minimize setups," Discrete Appl. Math. 134:351–360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c+1)/2, where c is the number of colors. This improves upon Tovey's c-approximation.

The final version of this article can be found at

Source: Discrete Applied Mathematics
Exact Citation:
Correa, José, Samuel Fiorini, and Nicolás E. Stier-Moses. "A Note on the Precedence-Constrained Class Sequencing Problem." Discrete Applied Mathematics 155, no. 3 (February 2007): 257-259.
Volume: 155
Number: 3
Pages: 257-259
Date: 2 2007