Burgess, Neil; Moore, M. A. Cost distributions in large combinatorial optimisation problems. (English) Zbl 0706.90064 J. Phys. A, Math. Gen. 22, No. 21, 4599-4609 (1989). Summary: We have examined the cost distribution of locally optimal solutions in certain combinatorial optimization problems. This distribution is found to be peaked about a value characteristic of the algorithm involved, with a width that decreases with the system size N. It is shown that the distribution of costs \(\epsilon\) is of the form exp(Ng(\(\epsilon\))) and that g(\(\epsilon\)) is self-averaging. Consequently, estimation of the optimal cost is best achieved by curve fitting to g(\(\epsilon\)). Possible forms for g(\(\epsilon\)) are proposed. MSC: 90C27 Combinatorial optimization 90C60 Abstract computational complexity for mathematical programming problems 90C06 Large-scale problems in mathematical programming Keywords:spin glass; travelling salesman; curve fitting; cost distribution; locally optimal solutions PDFBibTeX XMLCite \textit{N. Burgess} and \textit{M. A. Moore}, J. Phys. A, Math. Gen. 22, No. 21, 4599--4609 (1989; Zbl 0706.90064) Full Text: DOI Link