ANALYSIS OF HEURISTICS FOR NUMBER PARTITIONING

We illustrate the use of phase transition behavior in the study of heu ristics. Using an ''annealed'' theory, we define a parameter that meas ures the ''constrainedness'' of an ensemble of number partitioning pro blems. We identify a phase transition at a critical value of constrain edness. We then show that constrainedness can be used to analyze and c ompare algorithms and heuristics for number partitioning in a precise and quantitative manner. For example, we demonstrate that on uniform r andom 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 heu ristic. Our results refute a conjecture of Fu that phase transition be havior does not occur in number partitioning;. Additionally, they demo nstrate that phase transition behavior is useful for more than just si mple benchmarking. It can, for instance, be used to analyze heuristics , and to compare the quality of heuristic solutions.