A NEW INSIGHT INTO THE COFFMAN-GRAHAM ALGORITHM

Authors
BRASCHI B TRYSTRAM D
Citation
B. Braschi et D. Trystram, A NEW INSIGHT INTO THE COFFMAN-GRAHAM ALGORITHM, SIAM journal on computing, 23(3), 1994, pp. 662-669
Citations number
6
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
3
Year of publication
1994
Pages
662 - 669
Database
ISI
SICI code
0097-5397(1994)23:3<662:ANIITC>2.0.ZU;2-D
Abstract
The approximate solution of the m-machine problem is addressed. The La m-Sethi worst-case analysis of the Coffman-Graham algorithm is set up to be partly incorrect. A slightly different context is set up to corr ect and complete this analysis. It is shown that the makespan of a sch edule computed by an extended Coffman-Graham algorithm is lower than o r at worst equal to (2 - 2/m)omega(opt) - (m - 3)/m, where omega(opt) is the minimal makespan of a schedule.