A $(2 + \epsilon)$-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

Liya Yang; Ren\'e Sitters

arxiv: 1706.07604 · v1 · pith:QWMTVDCVnew · submitted 2017-06-23 · 💻 cs.DS · math.OC

A (2 + ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

Ren\'e Sitters , Liya Yang This is my paper

classification 💻 cs.DS math.OC

keywords timeapproximationcompletionepsilonmachineprecedencereleasesingle

0 comments

read the original abstract

We give a $(2 + \epsilon)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture made in [18]

This paper has not been read by Pith yet.

A (2 + ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

discussion (0)