MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kovács, Annamáriadblp
Editor(s):
Calamoneri, Tiziana
Finocchi, Irene
Italiano, Giuseppe F.		dblp
dblp
dblp
Not MPII Editor(s):
Calamoneri, Tiziana
Finocchi, Irene
Italiano, Giuseppe F.
BibTeX cite key*:
Kovacs2006
Title, Booktitle
Title*:
Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
Booktitle*:
Algorithms and Complexity : 6th Italian Conference, CIAC 2006
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/tw6p62x68728kq07/fulltext.pdf
Event Address*:
Rome, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
29 May 2006
Event End Date:
31 May 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3998
Number:
Month:
May
Pages:
187-198
Year*:
2006
VG Wort Pages:
20
ISBN/ISSN:
3-540-34375-X
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Q||C max denotes the problem of scheduling n jobs on m machines of different speeds such that the makespan is minimized. In the paper two special cases of Q||C max are considered: Case I, when m–1 machine speeds are equal, and there is only one faster machine; and Case II, when machine speeds are all powers of 2. Case I has been widely studied in the literature, while Case II is significant in an approach to design so called monotone algorithms for the scheduling problem.
We deal with the worst case approximation ratio of the classic list scheduling algorithm ’Longest Processing Time (LPT)’. We provide an analysis of this ratio Lpt/Opt for both special cases: For one fast machine, a tight bound of is given. When machine speeds are powers of 2 (2-divisible machines), we show that in the worst case 41/30 <Lpt/Opt<42/30=1.4.
To our knowledge, the best previous lower bound for both problems was 4/3–ε, whereas the best known upper bounds were 3/2–1/2m for Case I [6] resp. 3/2 for Case II [10]. For both the lower and the upper bound, the analysis of Case II is a refined version of that of Case I.
URL for the Abstract:
http://www.springerlink.com/content/tw6p62x68728kq07/
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{Kovacs2006,
AUTHOR = {Kov{\'a}cs, Annam{\'a}ria},
 EDITOR = {Calamoneri, Tiziana and Finocchi, Irene and Italiano, Giuseppe F.},
 TITLE = {Tighter Approximation Bounds for {LPT} Scheduling in Two Special Cases},
 BOOKTITLE = {Algorithms and Complexity : 6th Italian Conference, CIAC 2006},
 PUBLISHER = {Springer},
 YEAR = {2006},
 VOLUME = {3998},
 PAGES = {187--198},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Rome, Italy},
 MONTH = {May},
 ISBN = {3-540-34375-X},
}

Entry last modified by Ulrich Meyer, 03/02/2007
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)
Annamaria Kovacs		Created
06/27/2006 04:27:01 PM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Ulrich Meyer
Ulrich Meyer
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
03/02/2007 11:03:02 AM
03/02/2007 11:00:50 AM
07.02.2007 19:05:55
07.02.2007 17:32:55
22.09.2006 09:58:59