MPI-INF D1 Publications: Proceedings Article: Tighter Approximation Bounds for LPT Scheduling in Two Special Cases

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

Options:

Goto entry point

Author, Editor

Author(s):

Kovács, Annamária

dblp

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

URL of the conference:
URL for downloading the paper:	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:


(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

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

Attachment Section