We outline a technique for studying phase transition behaviour in computational problems using number partitioning as a case study. We first build an 'annealed' theory that assumes independence between parts of the number partition problem. Using this the theory, we identify a parameter which represents the ‘constrainedness’ of a number partition problem. We determine experimentally the critical value of this parameter at which a rapid transition between soluble and insoluble problems occurs. Finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value. We identify phase transition behaviour in both the decision and optimization versions of number partitioning, in the size of the optimal partition, and in the quality of heuristic solutions. This case study demonstrates how annealed theories and finite-size scaling allow us to compare algorithms and heuristics in a precise and quantitative manner

Phase Transitions and Annealed Theories: Number Partitioning as a Case Study

1996

Abstract

We outline a technique for studying phase transition behaviour in computational problems using number partitioning as a case study. We first build an 'annealed' theory that assumes independence between parts of the number partition problem. Using this the theory, we identify a parameter which represents the ‘constrainedness’ of a number partition problem. We determine experimentally the critical value of this parameter at which a rapid transition between soluble and insoluble problems occurs. Finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value. We identify phase transition behaviour in both the decision and optimization versions of number partitioning, in the size of the optimal partition, and in the quality of heuristic solutions. This case study demonstrates how annealed theories and finite-size scaling allow us to compare algorithms and heuristics in a precise and quantitative manner
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/1207
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact