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.
Original language | English (US) |
---|---|
Pages (from-to) | 51-57 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 56 |
Issue number | 1 |
DOIs | |
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