Phys. Rev. Lett. 88, 017202 (2001) [4 pages]Critical Slowing Down in Polynomial Time AlgorithmsReceived 10 April 2001; published 17 December 2001 Combinatorial optimization algorithms that compute exact ground states for disordered magnets are seen to exhibit critical slowing down at zero temperature phase transitions. Using the physical features of the models, such as vanishing stiffness on one side of the transition and the ground state degeneracy, the number of operations needed in the push-relabel algorithm for the random field Ising model and in the algorithm for the 2D spin glass is estimated. These results strengthen the connections between algorithms and the physical picture and may be used to improve the speed of computations. © 2002 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevLett.88.017202
DOI:
10.1103/PhysRevLett.88.017202
PACS:
75.10.Nr, 02.70.-c, 05.50.+q, 75.40.Mg
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.