Phase transition in the assignment problem for random matricesJ. G. Esteve and F. Falceto
Departamento de Física Teórica, Universidad de Zaragoza - Zaragoza, Spain and Instituto de Biocomputación y Física de Sistemas Complejos, Universidad de Zaragoza Zaragoza, Spain
received 6 July 2005; accepted in final form 30 September 2005
published online 26 October 2005
We report an analytic and numerical study of a phase transition in a P problem (the assignment problem) that separates two phases whose representatives are the simple matching problem (an easy P problem) and the traveling-salesman problem (a NP-complete problem). Like other phase transitions found in combinatoric problems (K-satisfiability, number partitioning) this can help to understand the nature of the difficulties in solving NP problems an to find more accurate algorithms for them.
02.60.Pn - Numerical optimization.
02.70.Rr - General statistical methods.
64.60.Cn - Order-disorder transformations; statistical mechanics of model systems.
© EDP Sciences 2005