File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Nonclairvoyant speed scaling for flow and energy

TitleNonclairvoyant speed scaling for flow and energy
Authors
KeywordsCompetitive analysis
Online scheduling
Power management
Speed scaling
Issue Date2011
PublisherSpringer 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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/144870
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorEdmonds, Jen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorMarchettiSpaccamela, Aen_HK
dc.contributor.authorPruhs, Ken_HK
dc.date.accessioned2012-02-21T05:43:45Z-
dc.date.available2012-02-21T05:43:45Z-
dc.date.issued2011en_HK
dc.identifier.citationAlgorithmica (New York), 2011, v. 61 n. 3, p. 507-517en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/144870-
dc.description.abstractWe 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.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmica (New York)en_HK
dc.rightsThe Author(s)en_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong Licenseen_US
dc.subjectCompetitive analysisen_HK
dc.subjectOnline schedulingen_HK
dc.subjectPower managementen_HK
dc.subjectSpeed scalingen_HK
dc.titleNonclairvoyant speed scaling for flow and energyen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturepublished_or_final_versionen_US
dc.identifier.doi10.1007/s00453-010-9420-2en_HK
dc.identifier.scopuseid_2-s2.0-80052860798en_HK
dc.identifier.hkuros194063-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80052860798&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume61en_HK
dc.identifier.issue3en_HK
dc.identifier.spage507en_HK
dc.identifier.epage517en_HK
dc.identifier.eissn1432-0541en_US
dc.identifier.isiWOS:000293962400001-
dc.publisher.placeUnited Statesen_HK
dc.description.otherSpringer Open Choice, 21 Feb 2012en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridEdmonds, J=7102594589en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridMarchettiSpaccamela, A=7004071298en_HK
dc.identifier.scopusauthoridPruhs, K=6603866438en_HK
dc.identifier.citeulike7415705-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats