Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtim...
Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime
About this item
Full title
Author / Creator
Publisher
New York: Springer US
Journal title
Language
English
Formats
Publication information
Publisher
New York: Springer US
Subjects
More information
Scope and Contents
Contents
In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime-optimal schedules, called the LD algorithm, has a simple worst-case performance bound:
5
m
-
2
4
m
-
1
, where
m
is the number of machines. We study the str...
Alternative Titles
Full title
Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime
Authors, Artists and Contributors
Author / Creator
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_proquest_miscellaneous_1845810510
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_proquest_miscellaneous_1845810510
Other Identifiers
ISSN
1094-6136
E-ISSN
1099-1425
DOI
10.1007/s10951-015-0467-4
