File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973068.134
- Scopus: eid_2-s2.0-70349094443
Supplementary
-
Citations:
- Scopus: 44
- 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 ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 1238-1244 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 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 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 | 2010-09-17T10:53:02Z | - |
dc.date.available | 2010-09-17T10:53:02Z | - |
dc.date.issued | 2009 | en_HK |
dc.identifier.citation | The 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, N.Y., 4-6 January 2009. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, p. 1238-1244 | en_HK |
dc.identifier.isbn | 978-089871680-1 | - |
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 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.language | eng | en_HK |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.rights | © 2009 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms in 2009, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
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.doi | 10.1137/1.9781611973068.134 | - |
dc.identifier.scopus | eid_2-s2.0-70349094443 | en_HK |
dc.identifier.hkuros | 181822 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-70349094443&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 1238 | en_HK |
dc.identifier.epage | 1244 | en_HK |
dc.identifier.scopusauthorid | Bansal, N=7102714084 | en_HK |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |