Standard combinatorial optimization problems

The setting is a finite graph with edge-lengths. Any set of edges has a ``total length", the sum of lengths of edges in the set. The problems we consider have the same general format: minimize the total length of an edge-set, over all edge-sets satisfying some specified requirement. Here are three alternate requirements. So if the graph has n vertices, then a matching has n/2 edges (and n must be even), a tour has n edges, and a spanning tree has n-1 edges. The corresponding problems are called the last being more evocative than ``minimum tour". Any introductory textbook on algorithms will mention these types of problems.

Analogous problems on the PWIT

Formulating the analogous problems on the PWIT (or any other infinite graph) involves two issues. First, we need to study infinite edge-sets, so instead of considering total edge-length we consider average edge-length, and there are some technicalities involved in defining this precisely. Second, the definitions of the requirements change slightly, as follows. ``Matching" is unchanged: ``Spanning tree" becomes And ``tour" becomes These are the objects we study on the PWIT, though we use the familiar names (MM, MST, TSP) instead of inventing more accurate acronyms.

Mathematical analysis of these problems on the PWIT

In talking about the solutions of these problems, we are talking about two different (though closely connected) things. There is a numerical value, which is the average edge-length in the minimal solution. And there is the minimal solution itself, as a random edge-set of the PWIT. The simulations are designed to show the minimal solution.

The numerical values have essentially been known for 20 years.

The MST value was discovered by Frieze (1985), who gave a rigorous proof based on the greedy algorithm for finding the MST. The value is actually the number zeta(3) = 1 + 1/8 + 1/27 + 1/64 + ...... The other values were discovered by Mezard and Parisi (1986, 1987) using the non-rigorous replica method and cavity method from statistical physics. The MM value is actually the number pi^2/6. The TSP value is derived numerically by solving a fixed point equation for probability distributions; it is not known whether there is an explicit formula.

Our own work, surveyed at a somewhat technical level in The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence reinterprets the Mezard-Parisi work in terms of mathematics on the PWIT, and forms the basis of the simulation methods used on this site.

Conceptually, previous work regarded these values as n tends to infinity limits of average edge-lengths in the stochastic mean-field model of distance. Our works reveals them as exact values within the PWIT.