RANDOMIZATION HELPS COMPUTING A MINIMUM SPANNING TREE UNDER UNCERTAINTY

作者：Megow Nicole^*; Meissner Julie; Skutella Martin

来源：SIAM Journal on Computing, 2017, 46(4): 1217-1240.

DOI：10.1137/16M1088375

• online algorithms
• competitive analysis
• minimum spanning tree
• randomized algorithms

Given a graph with "uncertainty intervals" on the edges, we want to identify a minimum spanning tree by querying some edges for their exact edge weights which lie in the given uncertainty intervals. Our objective is to minimize the number of edge queries. It is known that there is a deterministic algorithm with best possible competitive ratio 2 [T. Erlebach, et al., in Proceedings of STACS, Schloss Dagstuhl, Dagstuhl, Germany, 2008, pp. 277-288]. Our main result is a randomized algorithm with expected competitive ratio 1 + root 2 approximate to 1.707, solving the long-standing open problem of whether an expected competitive ratio strictly less than 2 can be achieved [T. Erlebach and M. Hoffmann, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 116 (2015)]. We also present novel results for various extensions, including arbitrary matroids and more general querying models.

• 出版日期2017