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 ” [17]. Specifically, we analyze a 3-competitive online algorithm [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 +