Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Bansal, Nikhil Chan, Ho-Leung dblp dblp Not MPG Author(s): Bansal, Nikhil
 Editor(s): Mathieu, Claire dblp Not MPII Editor(s): Mathieu, Claire
 BibTeX cite key*: Chan2008

 Title, Booktitle
 Title*: Weighted flow time does not admit O(1)-competitive algorithms Booktitle*: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)

 Event, URLs
 URL of the conference: http://www.siam.org/meetings/da09/ URL for downloading the paper: http://www.siam.org/proceedings/soda/2009/soda09.php Event Address*: New York, USA Language: English Event Date* (no longer used): Organization: ACM-SIAM Event Start Date: 4 January 2009 Event End Date: 6 January 2009

 Publisher
 Name*: ACM URL: Address*: New York, NY Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: Pages: 1238-1244 Year*: 2009 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 Note, Abstract, ©
 (LaTeX) 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 $\omega(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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Chan2008,
AUTHOR = {Bansal, Nikhil and Chan, Ho-Leung},
EDITOR = {Mathieu, Claire},
TITLE = {Weighted flow time does not admit O(1)-competitive algorithms},
BOOKTITLE = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009)},
PUBLISHER = {ACM},
YEAR = {2009},
ORGANIZATION = {ACM-SIAM},
PAGES = {1238--1244},
ADDRESS = {New York, USA},
}

Entry last modified by Anja Becker, 03/04/2010
Edit History (please click the blue arrow to see the details)

 Editor(s) [Library] Created 01/29/2009 11:04:07 AM Revisions 6. 5. 4. 3. 2. Editor(s) Anja Becker Anja Becker Ho-Leung Chan Ho-Leung Chan Ho-Leung Chan Edit Dates 01.03.2010 13:43:47 01.03.2010 12:39:09 2009/03/21 下午 04:24:09 2009/03/21 下午 04:23:14 2009/03/21 下午 04:22:05