A note on the precedence-constrained class sequencing problem
Lists
Only you see this
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.
BibTeX
@article{correa2007note,
author = {José R. Correa and Samuel Fiorini and Nicolás E. Stier Moses},
title = {{A note on the precedence-constrained class sequencing problem}},
journal = {Discret. Appl. Math.},
year = {2007},
doi = {10.1016/j.dam.2006.03.038},
}Loading related content...