Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on “the simplest (linear program) relaxation” (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal–dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.