Tighter bounds on a heuristic for a partition problem

Joseph Y.T. Leung; W. D. Wei

doi:10.1016/0020-0190(95)00099-X

Tighter bounds on a heuristic for a partition problem

Joseph Y.T. Leung, W. D. Wei

Research output: Contribution to journal › Article › peer-review

27 Scopus citations

Abstract

Chandra and Wong studied the following discrete minimization problem: Given a list of n positive real numbers, partition them into m parts so that Σq²_i is minimized, where q_i is the sum of all the numbers in the ith part. They showed that the worst-case ratio of the LPT rule (due to Graham), when applied to this minimization problem, has a worst-case performance bound of 25 24. In this article we prove tighter bounds for this algorithm.

Original language	English (US)
Pages (from-to)	51-57
Number of pages	7
Journal	Information Processing Letters
Volume	56
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(95)00099-X
State	Published - Oct 13 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Algorithms
Approximation algorithms
Discrete minimization
NP-hard
Partition
Storage allocation
Worst-case bound

Access to Document

10.1016/0020-0190(95)00099-X

Cite this

@article{4f71340d50a74c9ab7ed7be3cab5880b,

title = "Tighter bounds on a heuristic for a partition problem",

abstract = "Chandra and Wong studied the following discrete minimization problem: Given a list of n positive real numbers, partition them into m parts so that Σq2i is minimized, where qi is the sum of all the numbers in the ith part. They showed that the worst-case ratio of the LPT rule (due to Graham), when applied to this minimization problem, has a worst-case performance bound of 25 24. In this article we prove tighter bounds for this algorithm.",

keywords = "Algorithms, Approximation algorithms, Discrete minimization, NP-hard, Partition, Storage allocation, Worst-case bound",

author = "Leung, \{Joseph Y.T.\} and Wei, \{W. D.\}",

note = "Funding Information: * Research supported in part by the ONR grant NOO014-91-J-1383 Information Sciences at the University of Nebraska-Lincoln. {\textquoteright} Corresponding author. Emaik [email protected] {\textquoteright} On leave from Department of Mathematics,",

year = "1995",

month = oct,

day = "13",

doi = "10.1016/0020-0190(95)00099-X",

language = "English (US)",

volume = "56",

pages = "51--57",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Tighter bounds on a heuristic for a partition problem

AU - Leung, Joseph Y.T.

AU - Wei, W. D.

N1 - Funding Information: * Research supported in part by the ONR grant NOO014-91-J-1383 Information Sciences at the University of Nebraska-Lincoln. ’ Corresponding author. Emaik [email protected] ’ On leave from Department of Mathematics,

PY - 1995/10/13

Y1 - 1995/10/13

N2 - Chandra and Wong studied the following discrete minimization problem: Given a list of n positive real numbers, partition them into m parts so that Σq2i is minimized, where qi is the sum of all the numbers in the ith part. They showed that the worst-case ratio of the LPT rule (due to Graham), when applied to this minimization problem, has a worst-case performance bound of 25 24. In this article we prove tighter bounds for this algorithm.

AB - Chandra and Wong studied the following discrete minimization problem: Given a list of n positive real numbers, partition them into m parts so that Σq2i is minimized, where qi is the sum of all the numbers in the ith part. They showed that the worst-case ratio of the LPT rule (due to Graham), when applied to this minimization problem, has a worst-case performance bound of 25 24. In this article we prove tighter bounds for this algorithm.

KW - Algorithms

KW - Approximation algorithms

KW - Discrete minimization

KW - NP-hard

KW - Partition

KW - Storage allocation

KW - Worst-case bound

UR - https://www.scopus.com/pages/publications/0006822532

UR - https://www.scopus.com/inward/citedby.url?scp=0006822532&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(95)00099-X

DO - 10.1016/0020-0190(95)00099-X

M3 - Article

AN - SCOPUS:0006822532

SN - 0020-0190

VL - 56

SP - 51

EP - 57

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Tighter bounds on a heuristic for a partition problem

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this