File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1016/j.jda.2005.03.005
 Scopus: eid_2s2.033646487268
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Online competitive algorithms for maximizing weighted throughput of unit jobs
Title  Online competitive algorithms for maximizing weighted throughput of unit jobs 

Authors  
Keywords  Buffer Management Online Algorithms Scheduling 
Issue Date  2006 
Publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda 
Citation  Journal Of Discrete Algorithms, 2006, v. 4 n. 2, p. 255276 How to Cite? 
Abstract  We study an online unitjob scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unitjob scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e / ( e  1 ) ≈ 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider sbounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25competitive randomized algorithm for 2bounded instances, matching the known lower bound. We also give a deterministic algorithm Edfα, whose competitive ratio on sbounded instances is 2  2 / s + o ( 1 / s ). For 3bounded instances its ratio is φ{symbol} ≈ 1.618, matching the known lower bound. In suniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25competitive on suniform instances, if the span s is unbounded. For s = 2, our proof gives a lower bound of 4  2 sqrt(2) ≈ 1.172. Also, in the 2uniform case, we prove a lower bound of sqrt(2) ≈ 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 / ( 1  ( frac(m, m + 1) )m )competitive algorithm for m processors. We also show improved lower bounds for the general and suniform cases. © 2005 Elsevier B.V. All rights reserved. 
Persistent Identifier  http://hdl.handle.net/10722/152334 
ISSN  2015 SCImago Journal Rankings: 0.764 
References 
DC Field  Value  Language 

dc.contributor.author  Chin, FYL  en_US 
dc.contributor.author  Chrobak, M  en_US 
dc.contributor.author  Fung, SPY  en_US 
dc.contributor.author  Jawor, W  en_US 
dc.contributor.author  Sgall, J  en_US 
dc.contributor.author  Tichý, T  en_US 
dc.date.accessioned  20120626T06:37:15Z   
dc.date.available  20120626T06:37:15Z   
dc.date.issued  2006  en_US 
dc.identifier.citation  Journal Of Discrete Algorithms, 2006, v. 4 n. 2, p. 255276  en_US 
dc.identifier.issn  15708667  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/152334   
dc.description.abstract  We study an online unitjob scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unitjob scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e / ( e  1 ) ≈ 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider sbounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25competitive randomized algorithm for 2bounded instances, matching the known lower bound. We also give a deterministic algorithm Edfα, whose competitive ratio on sbounded instances is 2  2 / s + o ( 1 / s ). For 3bounded instances its ratio is φ{symbol} ≈ 1.618, matching the known lower bound. In suniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25competitive on suniform instances, if the span s is unbounded. For s = 2, our proof gives a lower bound of 4  2 sqrt(2) ≈ 1.172. Also, in the 2uniform case, we prove a lower bound of sqrt(2) ≈ 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 / ( 1  ( frac(m, m + 1) )m )competitive algorithm for m processors. We also show improved lower bounds for the general and suniform cases. © 2005 Elsevier B.V. All rights reserved.  en_US 
dc.language  eng  en_US 
dc.publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda  en_US 
dc.relation.ispartof  Journal of Discrete Algorithms  en_US 
dc.subject  Buffer Management  en_US 
dc.subject  Online Algorithms  en_US 
dc.subject  Scheduling  en_US 
dc.title  Online competitive algorithms for maximizing weighted throughput of unit jobs  en_US 
dc.type  Article  en_US 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_US 
dc.identifier.authority  Chin, FYL=rp00105  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.doi  10.1016/j.jda.2005.03.005  en_US 
dc.identifier.scopus  eid_2s2.033646487268  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033646487268&selection=ref&src=s&origin=recordpage  en_US 
dc.identifier.volume  4  en_US 
dc.identifier.issue  2  en_US 
dc.identifier.spage  255  en_US 
dc.identifier.epage  276  en_US 
dc.publisher.place  Netherlands  en_US 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_US 
dc.identifier.scopusauthorid  Chrobak, M=7005681296  en_US 
dc.identifier.scopusauthorid  Fung, SPY=7201970079  en_US 
dc.identifier.scopusauthorid  Jawor, W=6508003946  en_US 
dc.identifier.scopusauthorid  Sgall, J=7004376132  en_US 
dc.identifier.scopusauthorid  Tichý, T=36804279600  en_US 