Cost distributions in large combinatorial optimisation problems

The authors have examined the cost distribution of locally optimal solutions in certain combinatorial optimisation problems. This distribution is found to be peaked about a value characteristics 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.