File Download
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Weighted flow time does not admit O(1)competitive algorithms
Title  Weighted flow time does not admit O(1)competitive algorithms 

Authors  
Issue Date  2009 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the 20th ACMSIAM Symposium on Discrete Algorithms, 2009, p. 12381244 How to Cite? 
Abstract  We 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 nontrivial algorithms with polylogarithmic 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 Identifier  http://hdl.handle.net/10722/92650 
ISBN  
References 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.date.accessioned  20100917T10:53:02Z   
dc.date.available  20100917T10:53:02Z   
dc.date.issued  2009  en_HK 
dc.identifier.citation  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the 20th ACMSIAM Symposium on Discrete Algorithms, 2009, p. 12381244  en_HK 
dc.identifier.isbn  9780898716801   
dc.identifier.uri  http://hdl.handle.net/10722/92650   
dc.description.abstract  We 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 nontrivial algorithms with polylogarithmic 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.language  eng  en_HK 
dc.publisher  Society for Industrial and Applied Mathematics.   
dc.relation.ispartof  Proceedings of the 20th Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.rights  Proceedings of the 12th Annual ACMSIAM Symposium on Discrete Algorithms. Copyright © Society for Industrial and Applied Mathematics.   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.title  Weighted flow time does not admit O(1)competitive algorithms  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.description.nature  postprint   
dc.identifier.scopus  eid_2s2.070349094443  en_HK 
dc.identifier.hkuros  181822   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.070349094443&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  1238  en_HK 
dc.identifier.epage  1244  en_HK 
dc.description.other  The 20th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 46 January 2009. In Proceedings of the 20th ACMSIAM Symposium on Discrete Algorithms, 2009, p. 12381244   
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 