File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Online competitive algorithms for maximizing weighted throughput of unit jobs

TitleOnline competitive algorithms for maximizing weighted throughput of unit jobs
Authors
KeywordsBuffer Management
Online Algorithms
Scheduling
Issue Date2006
PublisherElsevier 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. 255-276 How to Cite?
AbstractWe study an online unit-job 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 unit-job 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 s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edfα, whose competitive ratio on s-bounded instances is 2 - 2 / s + o ( 1 / s ). For 3-bounded instances its ratio is φ{symbol} ≈ 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform 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 2-uniform 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 s-uniform cases. © 2005 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152334
ISSN
2015 SCImago Journal Rankings: 0.764
References

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_US
dc.contributor.authorChrobak, Men_US
dc.contributor.authorFung, SPYen_US
dc.contributor.authorJawor, Wen_US
dc.contributor.authorSgall, Jen_US
dc.contributor.authorTichý, Ten_US
dc.date.accessioned2012-06-26T06:37:15Z-
dc.date.available2012-06-26T06:37:15Z-
dc.date.issued2006en_US
dc.identifier.citationJournal Of Discrete Algorithms, 2006, v. 4 n. 2, p. 255-276en_US
dc.identifier.issn1570-8667en_US
dc.identifier.urihttp://hdl.handle.net/10722/152334-
dc.description.abstractWe study an online unit-job 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 unit-job 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 s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edfα, whose competitive ratio on s-bounded instances is 2 - 2 / s + o ( 1 / s ). For 3-bounded instances its ratio is φ{symbol} ≈ 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform 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 2-uniform 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 s-uniform cases. © 2005 Elsevier B.V. All rights reserved.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jdaen_US
dc.relation.ispartofJournal of Discrete Algorithmsen_US
dc.subjectBuffer Managementen_US
dc.subjectOnline Algorithmsen_US
dc.subjectSchedulingen_US
dc.titleOnline competitive algorithms for maximizing weighted throughput of unit jobsen_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/j.jda.2005.03.005en_US
dc.identifier.scopuseid_2-s2.0-33646487268en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33646487268&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume4en_US
dc.identifier.issue2en_US
dc.identifier.spage255en_US
dc.identifier.epage276en_US
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridChrobak, M=7005681296en_US
dc.identifier.scopusauthoridFung, SPY=7201970079en_US
dc.identifier.scopusauthoridJawor, W=6508003946en_US
dc.identifier.scopusauthoridSgall, J=7004376132en_US
dc.identifier.scopusauthoridTichý, T=36804279600en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats