2014/03/03 by Mestre, Julián, Verschae, José
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1403.0298
We consider a single machine scheduling problem that seeks to minimize a generalized cost function: given a subset of jobs we must order them so as to minimize ∑ fj(Cj), where Cj is the completion time of job j and fj is a job-dependent cost function. This problem has received a considerably amount of attention lately, partly because it generalizes a large number of sequencing problems while still allowing constant approximation guarantees. In a recent paper, Cheung and Shmoys provided a primal-dual algorithm for the problem and claimed that is a 2-approximation. In this paper we show that their analysis cannot yield an approximation guarantee better than 4. We then cast their algorithm as a local ratio algorithm and show that in fact it has an approximation ratio of 4. Additionally, we consider a more general problem where jobs has release dates and can be preempted. For this version we give a 4κ-approximation algorithm where κ is the number of distinct release dates.