In this paper the minimum spanning tree problem with uncertain edge costs is
discussed. In order to model the uncertainty a discrete scenario set is
specified and a robust framework is adopted to choose a solution. The min-max,
min-max regret and 2-stage min-max versions of the problem are discussed. The
complexity and approximability of all these problems are explored. It is proved
that the min-max and min-max regret versions with nonnegative edge costs are
hard to approximate within $O(\log^{1-\epsilon} n)$ for any $\epsilon>0$ unless
the problems in NP have quasi-polynomial time algorithms. Similarly, the
2-stage min-max problem cannot be approximated within $O(\log n)$ unless the
problems in NP have quasi-polynomial time algorithms. In this paper randomized
LP-based approximation algorithms with performance ratio of $O(\log^2 n)$ for
min-max and 2-stage min-max problems are also proposed.