1. ScholarBank@NUS
  2. 1. Staff
  3. Staff Publications
Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1022904408360
DC FieldValue
dc.titleCompetitive on-line scheduling with Level of Service
dc.contributor.authorChang, E.-C.
dc.contributor.authorYap, C.
dc.date.accessioned2013-07-04T07:46:49Z
dc.date.available2013-07-04T07:46:49Z
dc.date.issued2003
dc.identifier.citationChang, 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
dc.identifier.issn10946136
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39667
dc.description.abstractMotivated 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1023/A:1022904408360
dc.sourceScopus
dc.subjectCompetitive analysis
dc.subjectLevel of service
dc.subjectOn-line scheduling
dc.typeArticle
dc.contributor.departmentCOMPUTATIONAL SCIENCE
dc.description.doi10.1023/A:1022904408360
dc.description.sourcetitleJournal of Scheduling
dc.description.volume6
dc.description.issue3
dc.description.page251-267
dc.identifier.isiut000221412600004
Appears in Collections:Staff Publications

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

Google ScholarTM

Check

Altmetric


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