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_2-s2.0-33646487268
- WOS: WOS:000213924100005
- Find via
Supplementary
- Citations:
- 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. 255-276 How to Cite? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/152334 |
ISSN | 2015 SCImago Journal Rankings: 0.764 |
ISI Accession Number ID | |
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 | 2012-06-26T06:37:15Z | - |
dc.date.available | 2012-06-26T06:37:15Z | - |
dc.date.issued | 2006 | en_US |
dc.identifier.citation | Journal Of Discrete Algorithms, 2006, v. 4 n. 2, p. 255-276 | en_US |
dc.identifier.issn | 1570-8667 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/152334 | - |
dc.description.abstract | 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. | 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_2-s2.0-33646487268 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-33646487268&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.identifier.isi | WOS:000213924100005 | - |
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 |