Dimitris Bertsimas Probabilistic Minimum Spanning Tree Problem

Annotation

Whilst the greatest effort has been made to ensure the quality of this text, due to the historical nature of this content, in some rare cases there may be minor issues with legibility. In this paper we consider a natural probabilistic variation of the classical minimum spanning tree (MST) problem, which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed form expression for the expected length of a given spanning tree. Based on these expressions we prove that the problem is N P - complete. We further examine some combinatorial properties of the problem, establish the relation of the PMST problem with the MST problem and the network design problem and examine some cases where the problem is solvable in polynomial time.