##### File Download

There are no files associated with this item.

##### Supplementary
• 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 Chin, FYLChrobak, MFung, SPYJawor, WSgall, JTichý, T Buffer ManagementOnline AlgorithmsScheduling 2006 Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda Journal Of Discrete Algorithms, 2006, v. 4 n. 2, p. 255-276 How to Cite? We 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. http://hdl.handle.net/10722/152334 1570-86672015 SCImago Journal Rankings: 0.764 References in Scopus

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