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
Issue Date2004
PublisherSpringer 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. 187-198 How to Cite?
AbstractWe study an online scheduling problem for unit-length 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 s-bounded instances where the span of each job is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, and a deterministic algorithm EDFα, whose competitive ratio on s-bounded instances is at most 2 -2/s + o(l/s). For 3-bounded instances its ratio is φ≈ 1.618, matching the lower bound. We also consider 2-uniform 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 2-uniform cases. © Springer-Verlag 2004.
Persistent Identifierhttp://hdl.handle.net/10722/89011
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorBartal, Yen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorChrobak, Men_HK
dc.contributor.authorFung, SPYen_HK
dc.contributor.authorJawor, Wen_HK
dc.contributor.authorLavi, Ren_HK
dc.contributor.authorSgall, Jen_HK
dc.contributor.authorTichy, Ten_HK
dc.date.accessioned2010-09-06T09:51:16Z-
dc.date.available2010-09-06T09:51:16Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 2996, p. 187-198en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89011-
dc.description.abstractWe study an online scheduling problem for unit-length 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 s-bounded instances where the span of each job is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, and a deterministic algorithm EDFα, whose competitive ratio on s-bounded instances is at most 2 -2/s + o(l/s). For 3-bounded instances its ratio is φ≈ 1.618, matching the lower bound. We also consider 2-uniform 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 2-uniform cases. © Springer-Verlag 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsJournal of Discrete Algorithms. Copyright © Elsevier BV.en_HK
dc.titleOnline competitive algorithms for maximizing weighted throughput of unit jobsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1570-8667&volume=4&issue=2&spage=255&epage=276&date=2006&atitle=Online+Competitive+Algorithms+for+Maximizing+Weighted+Throughput+of+Unit+Jobsen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35048864369en_HK
dc.identifier.hkuros117582en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048864369&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume2996en_HK
dc.identifier.spage187en_HK
dc.identifier.epage198en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridBartal, Y=7006542888en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridChrobak, M=7005681296en_HK
dc.identifier.scopusauthoridFung, SPY=7201970079en_HK
dc.identifier.scopusauthoridJawor, W=6508003946en_HK
dc.identifier.scopusauthoridLavi, R=8615275900en_HK
dc.identifier.scopusauthoridSgall, J=7004376132en_HK
dc.identifier.scopusauthoridTichy, T=36804279600en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats