Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143231 | Operations Research Letters | 2007 | 5 Pages |
Abstract
We consider a single machine scheduling problem with two min-sum objective functions: the sum of completion times and the sum of weighted completion times. We propose a simple polynomial time (1+(1/γ),1+γ)-approximation algorithm, and show that for γ>1, there is no (x,y)-approximation with 1
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Eric Angel, Evripidis Bampis, Aleksei V. Fishkin,