Analysis of Heuristics for Number Partitioning

Research output: Contribution to journalArticlepeer-review

48 Citations (Scopus)

Abstract

We illustrate the use of phase transition behavior in the study of heuristics. Using an "annealed" theory, we define a parameter that measures the "constrainedness" of an ensemble of number partitioning problems. We identify a phase transition at a critical value of constrainedness. We then show that constrainedness can be used to analyze and compare algorithms and heuristics for number partitioning in a precise and quantitative manner. For example, we demonstrate that on uniform random problems both the Karmarkar-Karp and greedy heuristics minimize the constrainedness, but that the decisions made by the Karmarkar-Karp heuristic are superior at reducing constrainedness. This supports the better performance observed experimentally for the Karmarkar-Karp heuristic. Our results refute a conjecture of Fu that phase transition behavior does not occur in number partitioning;. Additionally, they demonstrate that phase transition behavior is useful for more than just simple benchmarking. It can, for instance, be used to analyze heuristics, and to compare the quality of heuristic solutions.

Original languageEnglish
Pages (from-to)430-451
Number of pages22
JournalComputational Intelligence
Volume14
Issue number2
DOIs
Publication statusPublished - Aug 1998

Keywords

  • heuristics
  • number partitioning
  • phase transitions
  • CRITICAL-BEHAVIOR
  • SATISFIABILITY

Fingerprint

Dive into the research topics of 'Analysis of Heuristics for Number Partitioning'. Together they form a unique fingerprint.

Cite this