A note on the precedence-constrained class sequencing problem

José R. Correa, Samuel Fiorini, Nicolás E. Stier MosesDiscret. Appl. Math 2007 · DOI · OpenReview

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

Figure