TIGHTER BOUNDS ON A HEURISTIC FOR A PARTITION PROBLEM

Authors
LEUNG JYT WEI WD
Citation
Jyt. Leung et Wd. Wei, TIGHTER BOUNDS ON A HEURISTIC FOR A PARTITION PROBLEM, Information processing letters, 56(1), 1995, pp. 51-57
Citations number
3
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
1
Year of publication
1995
Pages
51 - 57
Database
ISI
SICI code
0020-0190(1995)56:1<51:TBOAHF>2.0.ZU;2-3
Abstract
Chandra and Wong studied the following discrete minimization problem: Given a list of n positive real numbers, partition them into m parts s o that Sigma q(i)(2) is minimized, where q(i) is the sum of all the nu mbers in the ith part. They showed that the worst-case ratio of the LP T rule (due to Graham), when applied to this minimization problem, has a worst-case performance bound of 25/24. In this article we prove tig hter bounds for this algorithm.