An average case analysis of a greedy algorithm for the on-line Steiner tree problem

Imase, 1991, Dynamic Steiner tree problem, SIAM J. Disc. Math., 4, 369, 10.1137/0404033 Alon, 1992, On-line Steiner trees in the Euclidean plane Sleator, 1985, Amortized efficiency of list update and paging rules, Commun. ACM, 28, 202, 10.1145/2786.2793 Bertsimas, 1990, An asymptotic determination of the minimum spanning tree and minimum constants in geometrical probability, Operations Research Letters, 9, 223, 10.1016/0167-6377(90)90066-E Wang, 1989, An upper bound for the average length of the Euclidean minimum spanning tree, Intern. J. Computer Math., 30, 1, 10.1080/00207168908803765 Du, 1992, A proof of the Gilbert-Pollak conjecture on the Steiner ratio, Algorithmica, 7, 121, 10.1007/BF01758755 Hogg, 1978