File Download
There are no files associated with this item.
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  
Issue Date  2004 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 2996, p. 187198 How to Cite? 
Abstract  We study an online scheduling problem for unitlength jobs, where each job is specified by its release time, deadline, and a nonnegative weight. The goal is to maximize the weighted throughput, that is the total weight of scheduled jobs. We first give a randomized algorithm RMix with competitive ratio of e/(e 1) ≈1.582. Then we consider sbounded instances where the span of each job is at most s. We give a 1.25competitive randomized algorithm for 2bounded instances, and a deterministic algorithm EDFα, whose competitive ratio on sbounded instances is at most 2 2/s + o(l/s). For 3bounded instances its ratio is φ≈ 1.618, matching the lower bound. We also consider 2uniform instances, where the span of each job is 2. We prove a lower bounds for randomized algorithms and deterministic memoryless algorithms. Finally, we consider the multiprocessor case and give an 1/(1 (m/m+1) M)competitive algorithm for M processors. We also show improved lower bounds for the general and 2uniform cases. © SpringerVerlag 2004. 
Persistent Identifier  http://hdl.handle.net/10722/89011 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Bartal, Y  en_HK 
dc.contributor.author  Chin, FYL  en_HK 
dc.contributor.author  Chrobak, M  en_HK 
dc.contributor.author  Fung, SPY  en_HK 
dc.contributor.author  Jawor, W  en_HK 
dc.contributor.author  Lavi, R  en_HK 
dc.contributor.author  Sgall, J  en_HK 
dc.contributor.author  Tichy, T  en_HK 
dc.date.accessioned  20100906T09:51:16Z   
dc.date.available  20100906T09:51:16Z   
dc.date.issued  2004  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 2996, p. 187198  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/89011   
dc.description.abstract  We study an online scheduling problem for unitlength jobs, where each job is specified by its release time, deadline, and a nonnegative weight. The goal is to maximize the weighted throughput, that is the total weight of scheduled jobs. We first give a randomized algorithm RMix with competitive ratio of e/(e 1) ≈1.582. Then we consider sbounded instances where the span of each job is at most s. We give a 1.25competitive randomized algorithm for 2bounded instances, and a deterministic algorithm EDFα, whose competitive ratio on sbounded instances is at most 2 2/s + o(l/s). For 3bounded instances its ratio is φ≈ 1.618, matching the lower bound. We also consider 2uniform instances, where the span of each job is 2. We prove a lower bounds for randomized algorithms and deterministic memoryless algorithms. Finally, we consider the multiprocessor case and give an 1/(1 (m/m+1) M)competitive algorithm for M processors. We also show improved lower bounds for the general and 2uniform cases. © SpringerVerlag 2004.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.rights  Journal of Discrete Algorithms. Copyright © Elsevier BV.  en_HK 
dc.title  Online competitive algorithms for maximizing weighted throughput of unit jobs  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=15708667&volume=4&issue=2&spage=255&epage=276&date=2006&atitle=Online+Competitive+Algorithms+for+Maximizing+Weighted+Throughput+of+Unit+Jobs  en_HK 
dc.identifier.email  Chin, FYL:chin@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, FYL=rp00105  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.035048864369  en_HK 
dc.identifier.hkuros  117582  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.035048864369&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  2996  en_HK 
dc.identifier.spage  187  en_HK 
dc.identifier.epage  198  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Bartal, Y=7006542888  en_HK 
dc.identifier.scopusauthorid  Chin, FYL=7005101915  en_HK 
dc.identifier.scopusauthorid  Chrobak, M=7005681296  en_HK 
dc.identifier.scopusauthorid  Fung, SPY=7201970079  en_HK 
dc.identifier.scopusauthorid  Jawor, W=6508003946  en_HK 
dc.identifier.scopusauthorid  Lavi, R=8615275900  en_HK 
dc.identifier.scopusauthorid  Sgall, J=7004376132  en_HK 
dc.identifier.scopusauthorid  Tichy, T=36804279600  en_HK 