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.
- a matching is an edge-set such that each vertex is
in exactly one edge in the matching.
- a spanning tree is an edge set such that, for any pair
of vertices, there is a unique path between them which uses edges
from the spanning tree.
- a tour is an edge-set making a path which passes through
each vertex exactly once, ending at its starting vertex.
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
- Minimum matching (MM)
- Minimum spanning tree (MST)
- Traveling salesman problem (TSP)
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:
- a matching is an edge-set such that each vertex is
in exactly one edge in the matching.
``Spanning tree" becomes
- spanning forest, a set of trees such that each tree is
infinite and each vertex is in exactly one tree.
And ``tour" becomes
- path collection, a collection of doubly-infinite paths
such that each vertex appears exactly once (in some path).
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.
- 1.20 (MST)
- 1.64 (MM)
- 2.04 (TSP)
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.