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):

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:




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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section