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 Library locked




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section