Tighter bounds on a heuristic for a partition problem

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

Research output: Contribution to journalArticlepeer-review

25 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 Σ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 languageEnglish (US)
Pages (from-to)51-57
Number of pages7
JournalInformation Processing Letters
Volume56
Issue number1
DOIs
StatePublished - Oct 13 1995
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Tighter bounds on a heuristic for a partition problem'. Together they form a unique fingerprint.

Cite this