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:








Author, Editor

Author(s):

Kontogiannis, Spyros

dblp



Editor(s):





BibTeX cite key*:

Kontogiannis2002

Title, Booktitle

Title*:

Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-Size Tasks to Related Machines

Booktitle*:

Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02)

Event, URLs

URL of the conference:

http://omega.crm.umontreal.ca/STOC'02/

URL for downloading the paper:

http://www.mpi-sb.mpg.de/~spyros/papers/stoc02.ps.gz

Event Address*:

Montreal, Quebec, Canada

Language:

English

Event Date*
(no longer used):

-- May, 19-21, 2002

Organization:

ACM Special Interest Group on Algorithms and Computation Theory (ACM-SIGACT)

Event Start Date:

19 May 2002

Event End Date:

21 May 2002

Publisher

Name*:

ACM

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

May

Pages:

124-133

Year*:

2002

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

In this paper we study the problem of assigning unit-size tasks to
related machines when only limited online information is provided
to each task. This is a general framework whose special cases are
the classical multiple-choice games for the assignment of
unit-size tasks to identical machines. The latter case was the
subject of intensive research for the last decade. The problem is
intriguing in the sense that the natural extensions of the greedy
oblivious schedulers, which are known to achieve near-optimal
performance in the case of identical machines, are proved to
perform quite poorly in the case of the related machines.

In this work we present a rather surprising lower bound stating
that any oblivious scheduler that assigns an arbitrary number of
tasks to $n$ related machines would need $\Omega\left(\frac{\log
n}{\log\!\log n}\right)$ polls of machine loads per task, in order to
achieve a constant competitive ratio versus the optimum offline
assignment of the same input sequence to these machines. On the
other hand, we prove that the missing information for an oblivious
scheduler to perform almost optimally, is the amount of tasks to
be inserted into the system. In particular, we provide an
oblivious scheduler that only uses $\cal{O}(\log\!\log n)$ polls, along with
the additional information of the size of the input sequence, in
order to achieve a constant competitive ratio vs. the optimum
offline assignment. The philosophy of this scheduler is based on
an interesting exploitation of the {\sc slowfit} concept
([AAFPW97,BFN00,BCK97]; for a survey see
[BY98,Azar98,Sgall98]) for the assignment of the tasks to the
related machines despite the restrictions on the provided online
information, in combination with a layered induction argument for
bounding the tails of the number of tasks passing from slower to
faster machines. We finally use this oblivious scheduler as the
core of an adaptive scheduler that does not demand the knowledge
of the input sequence and yet achieves almost the same
performance.

URL for the Abstract:

http://www.mpi-sb.mpg.de/~spyros/papers/stoc02-abs.htm

Copyright Message:

Permission to make digital or hard copies of part or all of
this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or
commercial advantage and that copies bear this notice and the
full citation on the first page. Copyrights for components of
this work owned by others than ACM must be honored. Abstracting
with credit is permitted. To copy otherwise, to republish, to
post on servers or to redistribute to lists, requires prior
specific permission and/or a fee.


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kontogiannis2002,
AUTHOR = {Kontogiannis, Spyros},
TITLE = {Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-Size Tasks to Related Machines},
BOOKTITLE = {Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02)},
PUBLISHER = {ACM},
YEAR = {2002},
ORGANIZATION = {ACM Special Interest Group on Algorithms and Computation Theory (ACM-SIGACT)},
PAGES = {124--133},
ADDRESS = {Montreal, Quebec, Canada},
MONTH = {May},
}


Entry last modified by Uwe Brahm, 03/02/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)
Spyros Kontogiannis
Created
03/13/2002 09:09:36 AM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
10/16/2003 06:14:32 PM
10/16/2003 06:09:24 PM
28.08.2003 16:06:50
28.08.2003 16:05:47
18/10/2002 13:04:52
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section