On the random 2-stage minimum spanning tree Export

@article{citeulike:1302282, abstract = {It is known [A. M. Frieze, Discrete Appl Math 10 (1985), 47-56] that if the edge costs of the complete graph Kn are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to . Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs cM: E ? \ℝ and cT: E ? \ℝ, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs cM(e) and cT(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 cM(e), or to wait until its Tuesday price cT(e) appears. The set of edges XM bought on Monday is then completed by the set of edges XT 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 ?(3)/2 + o(1). We show that, in the case of two-stage optimization, the expected value of the optimal cost exceeds ?(3)/2 by an absolute constant \ϵ \> 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than ? and completes them on Tuesday in an optimal way, and show that the optimal choice for ? is ? = 1/n with the expected cost ?(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, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 - 1/e + o(1). {\copyright} 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006}, address = {Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Department of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel}, author = {Flaxman, Abraham D. and Frieze, Alan and Krivelevich, Michael}, citeulike-article-id = {1302282}, citeulike-linkout-0 = {http://dx.doi.org/10.1002/rsa.20079}, citeulike-linkout-1 = {http://www3.interscience.wiley.com/cgi-bin/abstract/110532669/ABSTRACT}, comment = {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.) }, doi = {10.1002/rsa.20079}, journal = {Random Structures and Algorithms}, keywords = {minimum, programming, random, spanning, stage, stochastic, tree, two}, number = {1}, pages = {24--36}, posted-at = {2007-05-17 15:30:11}, priority = {0}, title = {On the random 2-stage minimum spanning tree}, url = {http://dx.doi.org/10.1002/rsa.20079}, volume = {28}, year = {2006} }

TY - JOUR ID - citeulike:1302282 L3 - citeulike-article-id:1302282 N2 - It is known [A. M. Frieze, Discrete Appl Math 10 (1985), 47-56] that if the edge costs of the complete graph Kn are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to . Here we consider the following stochastic two-stage version of this optimization problem. There are two sets of edge costs cM: E ? ℝ and cT: E ? ℝ, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs cM(e) and cT(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 cM(e), or to wait until its Tuesday price cT(e) appears. The set of edges XM bought on Monday is then completed by the set of edges XT 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 ?(3)/2 + o(1). We show that, in the case of two-stage optimization, the expected value of the optimal cost exceeds ?(3)/2 by an absolute constant ϵ > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than ? and completes them on Tuesday in an optimal way, and show that the optimal choice for ? is ? = 1/n with the expected cost ?(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, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 - 1/e + o(1). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 IS - 1 JF - Random Structures and Algorithms AD - Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213; Department of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel EP - 36 TI - On the random 2-stage minimum spanning tree VL - 28 SP - 24 KW - minimum KW - programming KW - random KW - spanning KW - stage KW - stochastic KW - tree KW - two N1 - 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.) AU - Flaxman, Abraham AU - Frieze, Alan AU - Krivelevich, Michael PY - 2006/// UR - http://dx.doi.org/10.1002/rsa.20079 ER -