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: Goto entry point

 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:

 (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},