2016/12/10 by Maurice Cheung, Cheung, Maurice, Julián Mestre +6
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1612.03339
openalex publication_date 2016/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the following single-machine scheduling problem, which is often\ndenoted 1||\∑ fj: we are given n jobs to be scheduled on a single\nmachine, where each job j has an integral processing time pj, and there is\na nondecreasing, nonnegative cost function fj(Cj) that specifies the cost\nof finishing j at time Cj; the objective is to minimize \∑j=1n\nfj(Cj). Bansal & Pruhs recently gave the first constant approximation\nalgorithm with a performance guarantee of 16. We improve on this result by\ngiving a primal-dual pseudo-polynomial-time algorithm based on the recently\nintroduced knapsack-cover inequalities. The algorithm finds a schedule of cost\nat most four times the constructed dual solution. Although we show that this\nbound is tight for our algorithm, we leave open the question of whether the\nintegrality gap of the LP is less than 4. Finally, we show how the technique\ncan be adapted to yield, for any \ε >0, a (4+\ε )-approximation\nalgorithm for this problem.\n