File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Weighted flow time does not admit O(1)-competitive algorithms

TitleWeighted flow time does not admit O(1)-competitive algorithms
Authors
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 1238-1244 How to Cite?
AbstractWe consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job j has an arbitrary arrival time r j, weight w j and size p j, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an ω(1) lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly. Copyright © by SIAM.
Persistent Identifierhttp://hdl.handle.net/10722/92650
ISBN
References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorChan, HLen_HK
dc.date.accessioned2010-09-17T10:53:02Z-
dc.date.available2010-09-17T10:53:02Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 1238-1244en_HK
dc.identifier.isbn978-089871680-1-
dc.identifier.urihttp://hdl.handle.net/10722/92650-
dc.description.abstractWe consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job j has an arbitrary arrival time r j, weight w j and size p j, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an ω(1) lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly. Copyright © by SIAM.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.titleWeighted flow time does not admit O(1)-competitive algorithmsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.description.naturepostprint-
dc.identifier.scopuseid_2-s2.0-70349094443en_HK
dc.identifier.hkuros181822-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70349094443&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage1238en_HK
dc.identifier.epage1244en_HK
dc.description.otherThe 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 1238-1244-
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats