File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling

TitleExtra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
Authors
Issue Date2006
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 334-343 How to Cite?
AbstractWe study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (high-est density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using O(1) times unit-speed machines, are 1-competitive for flow time and stretch and O(1)-competitive for weighted flow time, respectively.
Persistent Identifierhttp://hdl.handle.net/10722/53611
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLiu, KSen_HK
dc.date.accessioned2009-04-03T07:24:37Z-
dc.date.available2009-04-03T07:24:37Z-
dc.date.issued2006en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 334-343en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/53611-
dc.description.abstractWe study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (high-est density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using O(1) times unit-speed machines, are 1-competitive for flow time and stretch and O(1)-competitive for weighted flow time, respectively.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe Annual ACM - S I A M Symposium on Discrete Algorithms Proceedings. Copyright © Society for Industrial and Applied Mathematics.en_HK
dc.titleExtra unit-speed machines are almost as powerful as speedy machines for competitive flow time schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=334&epage=343&date=2006&atitle=Extra+unit-speed+machines+are+almost+as+powerful+as+speedy+machines+for+competitive+flow+time+schedulingen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1145/1109557.1109595en_HK
dc.identifier.scopuseid_2-s2.0-33244454964en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33244454964&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage334en_HK
dc.identifier.epage343en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLiu, KS=8883021000en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats