On the random 2-stage minimum spanning tree

It was previously known that if the edge costs of the complete graph $K_n$ are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to $\zeta(3)=\sum_{i=1}^{\infty}i^{-3}$. Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs $c_M\colon E\rightarrow\mathbb{R}$ and $c_T\colon E\rightarrow\mathbb{R}$, called Monday's prices and Tuesday's prices, respectively. For each edge $e$, both costs $c_M(e)$ and $c_T(e)$ are independent random variables, uniformly distributed in $[0,1]$. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge $e$ whether to buy it at Monday's price $c_M(e)$, or to wait until its Tuesday price $c_T(e)$ appears. The set of edges $X_M$ bought on Monday is then completed by the set of edges $X_T$ bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost $\zeta(3)/2+o(1)$. We show that in the case of two-stage optimization, the expected value of the optimal cost exceeds $\zeta(3)/2$ by an absolute constant $\epsilon>0$. We also consider a threshold heuristic, where, on Monday, the algorithm buys edges of cost less than $\alpha$, and, on Tuesday, the algorithm completes the tree in an optimal way. We show that the optimal choice for $\alpha$ is $\alpha=1/n$ for which the expected cost is $\zeta(3)-1/2+o(1)$. The threshold heuristic is shown to be sub-optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out-arborescence rooted at a fixed vertex $r$. We show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value $1-1/e+o(1)$.

I find it quite intriguing that the limiting value of so many natural combinational optimization problems turn out to be miraculous constants related to Riemann's zeta function. The calculations which show that the solution found by the threshold heuristic has value asymptotic to $\zeta(3)-1/2$ is particularly miraculous (and unfortunately offers no ``reason'' why this value appears.)