On the solution of the random link matching problems
Authors:
- 1 January 1987
- journal article
- Published by EDP Sciences in Journal de Physique
- Vol. 48 (9) , 1451-1459
Abstract
We show that the replica symmetric solution of the matching problem (bipartite or not) with independent random distances is stable. We compute the fluctuations and get the O (1/N) corrections to the length of the optimal matching in a generic sampleKeywords
This publication has 8 references indexed in Scilit:
- Mean-Field Theory of Randomly Frustrated Systems with Finite ConnectivityEurophysics Letters, 1987
- Mean-field theory of spin-glasses with finite coordination numberPhysical Review Letters, 1987
- Replica Symmetric Solutions in the Ising Spin Glass: The Tree ApproximationEurophysics Letters, 1987
- SK Model: The Replica Solution without ReplicasEurophysics Letters, 1986
- A replica analysis of the travelling salesman problemJournal de Physique, 1986
- Configuration space analysis of travelling salesman problemsJournal de Physique, 1985
- Mean-field theory for optimization problemsJournal de Physique Lettres, 1985
- On the statistical mechanics of optimization problems of the travelling salesman typeJournal de Physique Lettres, 1984