A note on scheduling to meet two min-sum objectives Angel, Eric; Bampis, Evripidis; Fishkin, Aleksei V.

User activity

Share to:
View the summary of this work
Angel, Eric ; Bampis, Evripidis ; Fishkin, Aleksei V.
Appears In
Operations Research Letters
scheduling; [info:info_ro] computer science/operations research; [info:info_gt] computer science/computer science and game theory
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.orl.2006.01.004 Byline: Eric Angel (a), Evripidis Bampis (a), Aleksei V. Fishkin (b) 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/[gamma]),1+[gamma])-approximation algorithm, and show that for [gamma]1, there is no (x,y)-approximation with 1<x<1+(1/[gamma]) and 1<y<1+([gamma]-1)/(2+[gamma]). Author Affiliation: (a) LaMI, CNRS UMR 8042, Universite d'Evry Val d'Essonne, France (b) Department of Computer Science, University of Liverpool, Chadwick Building, Peach Street, Liverpool L69 7ZF, UK Article History: Received 9 June 2004; Accepted 16 January 2006
Work ID

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users