Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
复制标题
可探索不确定性下的最小生成树的理论与实验
DOI：
10.1145/3422371
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
J. Meißner
中科院分区：
文献类型：
--
作者：
J. Focke;N. Megow;J. Meißner
我们考虑不确定性模型中的最小生成树（MST）问题，其中可以探索区间边缘权重以获得准确的权重。任务是通过查询最小边数来找到 MST。这个问题已经受到算法理论界的相当多的关注。在本文中，我们对不确定性下的 MST 进行了首次实际实验，从理论上比较了三种已知算法，并将算法的理论与实际行为进行了比较。其中，我们观察到平均性能和查询的绝对数量都远离理论上的最坏情况界限。此外，我们研究了一种已知的通用预处理程序，并开发了一种最大限度地减少数据不确定性的实现。我们还描述了一类通过预处理解决最优问题的实例。我们的实验基于电信应用中的实际数据以及标准 TSPLib 图库生成的不确定性实例。
We consider the minimum spanning tree (MST) problem in an uncertainty model where interval edge weights can be explored to obtain the exact weight. The task is to find an MST by querying the minimum number of edges. This problem has received quite some attention from the algorithms theory community. In this article, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved to optimality by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.
登录
查看更多内容
选择的更新复杂度及相关问题
影响因子：
0.5
作者：
Manoj Gupta;Yogish Sabharwal;Sandeep Sen
通讯作者：
Sandeep Sen
计算具有不确定性的中位数
影响因子：
1
作者：
T. Feder;R. Motwani;R. Panigrahy;Christopher Olston;J. Widom
通讯作者：
J. Widom
计算具有不确定性的最短路径
DOI：
10.1016/j.jalgor.2004.07.005
发表时间：
2003
期刊：
J. Algorithms
影响因子：
--
作者：
T. Feder;R. Motwani;Liadan O'Callaghan;Christopher Olston;R. Panigrahy
通讯作者：
R. Panigrahy
用于不确定性计算的查询竞争算法
DOI：
--
发表时间：
2015
期刊：
Bull. EATCS
影响因子：
--
作者：
T. Erlebach;Michael Hoffmann
通讯作者：
Michael Hoffmann
查询的鲁棒背包问题
DOI：
10.1016/j.cor.2014.09.010
发表时间：
2015
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Goerigk;Schöbel
通讯作者：
Schöbel