Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
复制标题
DOI：
10.1007/978-3-662-48350-3_73
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Nicole Megow;Julie Meißner;M. Skutella
中科院分区：
文献类型：
--
作者：
Nicole Megow;Julie Meißner;M. Skutella
给定一个边缘上有“不确定区间”的图，我们希望通过查询位于给定不确定区间内的某些边的确切权值来识别最小生成树。我们的目标是最小化边查询的数量。已知存在一个具有最佳可能竞争比2 [T]的确定性算法。Erlebach, et ., in STACS proceedings, Schloss Dagstuhl, Dagstuhl, Germany, 2008, pp. 277—288]。我们的主要成果是一个具有期望竞争比的随机算法，解决了长期存在的期望竞争比是否能严格小于2的开放性问题[T]。Erlebach和M. Hoffmann,Bull。欧元。Assoc。定理。第一版。科学。生态学报，116(2015)]。我们还提出了各种扩展的新结果，包括任意拟阵和更一般的查询模型。
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., inProceedings of STACS, Schloss Dagstuhl, Dagstuhl, Germany, 2008, pp. 277--288]. Our main result is a randomized algorithm with expected competitive ratio, 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.