Online minimum spanning trees with random edge weights

Give every edge of the complete graph on $n$ vertices an independent uniform random weight. Frieze proved that the cheapest spanning tree has expected weight tending to $\zeta(3) \approx 1.202$. What if the edges are revealed one at a time, in random order, and each must be accepted or rejected on the spot? The best possible expected cost is believed to converge to a constant near 1.9, but even the existence of the limit is unproved.

Problem

Let $K_n$ be the complete graph on $n$ vertices. Its $\binom{n}{2}$ edges $e$ receive independent weights $W_e$, uniform on $[0, 1]$, and are presented one by one in uniformly random order. When an edge is presented its weight is revealed, and an online algorithm must decide immediately and irrevocably whether to add it to the forest built so far; at the end the accepted edges must form a spanning tree. Let

$$\mathrm{cost}(n) = \inf_{\text{online algorithms}} \mathbb{E}\big[\text{total weight of the accepted tree}\big].$$

Prove that $\mathrm{cost}(n)$ converges as $n \to \infty$, and determine the limit.

Aldous, Angel and Berestycki also use a Poisson version: the points $(t, x)$ of a Poisson process on $[0, 1] \times [0, \infty)$ are taken in time order, and at time $t$ a uniformly random edge is offered with weight $x$. This version has useful scaling and Markov properties.

Background

The offline problem is classical: Frieze (1985) showed that the expected weight of the minimum spanning tree tends to $\zeta(3)$. The online version asks how much is lost when decisions cannot wait. Aldous, Angel and Berestycki studied it in a 2008 draft, and Aldous has mentioned it to many people since; he posted it on his open problems page in 2018. The optimal online algorithm behaves like a time-inhomogeneous stochastic coalescent of tree components, which links the problem to the theory of coagulation equations.

What is known

• For each $n$, in the Poisson version, $\mathrm{cost}(n)$ can be computed from a recursion over partitions of $\{1, \dots, n\}$ giving the optimal expected cost starting from a forest with given components (Aldous, Angel and Berestycki, 2008 draft).
• Upper bound: $\limsup_n \mathrm{cost}(n) \le 4$ in the Poisson version, from explicit solutions of an associated system of inequalities; the simplest gives $\mathrm{cost}(n) \le 4(n-1)/n$.
• Lower bound: $\liminf_n \mathrm{cost}(n) \ge 1.368\ldots$ in either version, via variants of classical optimal online selection results.
• Numerics suggest that the limit is about 1.9. The authors conjecture that it exists and is determined by the solution of a partial differential equation on the infinite simplex. They also note that the two versions have not yet been proved to have the same asymptotic cost.

What would count as progress

• A proof that $\lim_n \mathrm{cost}(n)$ exists, in either version, even without identifying it.
• Better bounds: an explicit online algorithm with provable asymptotic cost below 4, or a lower bound above 1.368. Algorithms can be tested by simulation before analysis.
• Certified numerics: exact computation of $\mathrm{cost}(n)$ for larger $n$ from the partition recursion, with rigorous error control, or a justified derivation of the limiting equation.
• A proof that the combinatorial and Poisson versions have the same limit.

References

1. A. M. Frieze, On the value of a random minimum spanning tree problem, Discrete Appl. Math. 10 (1985), 47–56.
2. D. Aldous, O. Angel and N. Berestycki, Online random weight minimal spanning trees and a stochastic coalescent, draft (2008).

Source

Imported from David Aldous's open problems online_zeta3, curated by David Aldous. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.