A Note on the Precedence-Constrained Class Sequencing ProblemCoauthor(s): José Correa, Samuel Fiorini.
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 http://dx.doi.org/10.1016/j.dam.2006.03.038.
Source: Discrete Applied Mathematics
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.
Date: 2 2007