File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s00453-010-9420-2
- Scopus: eid_2-s2.0-80052860798
- WOS: WOS:000293962400001
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Nonclairvoyant speed scaling for flow and energy
Title | Nonclairvoyant speed scaling for flow and energy |
---|---|
Authors | |
Keywords | Competitive analysis Online scheduling Power management Speed scaling |
Issue Date | 2011 |
Publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm |
Citation | Algorithmica (New York), 2011, v. 61 n. 3, p. 507-517 How to Cite? |
Abstract | We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s α, LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and 2α 2 ln α for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive. © 2010 The Author(s). |
Persistent Identifier | http://hdl.handle.net/10722/144870 |
ISSN | 2022 Impact Factor: 1.1 2020 SCImago Journal Rankings: 0.647 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Edmonds, J | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Lee, LK | en_HK |
dc.contributor.author | MarchettiSpaccamela, A | en_HK |
dc.contributor.author | Pruhs, K | en_HK |
dc.date.accessioned | 2012-02-21T05:43:45Z | - |
dc.date.available | 2012-02-21T05:43:45Z | - |
dc.date.issued | 2011 | en_HK |
dc.identifier.citation | Algorithmica (New York), 2011, v. 61 n. 3, p. 507-517 | en_HK |
dc.identifier.issn | 0178-4617 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/144870 | - |
dc.description.abstract | We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s α, LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and 2α 2 ln α for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive. © 2010 The Author(s). | en_HK |
dc.language | eng | en_US |
dc.publisher | Springer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm | en_HK |
dc.relation.ispartof | Algorithmica (New York) | en_HK |
dc.rights | The Author(s) | en_US |
dc.subject | Competitive analysis | en_HK |
dc.subject | Online scheduling | en_HK |
dc.subject | Power management | en_HK |
dc.subject | Speed scaling | en_HK |
dc.title | Nonclairvoyant speed scaling for flow and energy | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4551/resserv?sid=springerlink&genre=article&atitle=Nonclairvoyant Speed Scaling for Flow and Energy&title=Algorithmica&issn=01784617&date=2011-11-01&volume=61&issue=3& spage=507&authors=Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, <i>et al.</i> | en_US |
dc.identifier.email | Chan, HL: hlchan@cs.hku.hk | en_HK |
dc.identifier.email | Lam, TW: hresltk@hkucc.hku.hk | en_HK |
dc.identifier.email | Lee, LK: lklee@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Lee, LK=rp00140 | en_HK |
dc.description.nature | published_or_final_version | en_US |
dc.identifier.doi | 10.1007/s00453-010-9420-2 | en_HK |
dc.identifier.scopus | eid_2-s2.0-80052860798 | en_HK |
dc.identifier.hkuros | 194063 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-80052860798&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 61 | en_HK |
dc.identifier.issue | 3 | en_HK |
dc.identifier.spage | 507 | en_HK |
dc.identifier.epage | 517 | en_HK |
dc.identifier.eissn | 1432-0541 | en_US |
dc.identifier.isi | WOS:000293962400001 | - |
dc.publisher.place | United States | en_HK |
dc.description.other | Springer Open Choice, 21 Feb 2012 | en_US |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | Edmonds, J=7102594589 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Lee, LK=12646190100 | en_HK |
dc.identifier.scopusauthorid | MarchettiSpaccamela, A=7004071298 | en_HK |
dc.identifier.scopusauthorid | Pruhs, K=6603866438 | en_HK |
dc.identifier.citeulike | 7415705 | - |
dc.identifier.issnl | 0178-4617 | - |