Nicolás Stier-Moses

A Note on the Precedence-Constrained Class Sequencing Problem

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

Download:

Adobe Acrobat PDF

Abstract:

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
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