Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1022904408360
Title: Competitive on-line scheduling with Level of Service
Authors: Chang, E.-C. 
Yap, C.
Keywords: Competitive analysis
Level of service
On-line scheduling
Issue Date: 2003
Source: Chang, E.-C., Yap, C. (2003). Competitive on-line scheduling with Level of Service. Journal of Scheduling 6 (3) : 251-267. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1022904408360
Abstract: Motivated by an application in thinwire visualization, we study an abstract on-line scheduling problem where the size of each requested service can be scaled down by the scheduler. Thus, our problem embodies a notion of "Level of Service" that is increasingly important in multimedia applications. We give two schedulers FirstFit and EndFit based on two simple heuristics, and generalize them into a class of greedy schedulers. We show that both FirstFit and EndFit are 2-competitive, and any greedy scheduler is 3-competitive. These bounds are shown to be tight.
Source Title: Journal of Scheduling
URI: http://scholarbank.nus.edu.sg/handle/10635/39667
ISSN: 10946136
DOI: 10.1023/A:1022904408360
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

5
checked on Dec 11, 2017

Page view(s)

41
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.