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

2017/06/23 by Sitters, René, Yang, Liya
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1706.07604

Abstract

We give a (2 + ε)-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]

Related

• A 2.542-Approximation for Precedence Constrained Single Machine\n Scheduling with Release Dates and Total Weighted Completion Time Objective
• Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs
• Approximation schemes for minimizing average weighted completion time with release dates
• Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
• Minimum total weighted completion time: Faster approximation schemes