LIPIcs.SEA.2017.22.pdf
- Filesize: 0.68 MB
- 14 pages
Document
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Authors
-
Part of:
Volume:
16th International Symposium on Experimental Algorithms (SEA 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-08-07
Cite As Get BibTex
Jacob Focke, Nicole Megow, and Julie Meißner. Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SEA.2017.22
Abstract
We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, 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 completely 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.
Subject Classification
Keywords
- MST
- explorable uncertainty
- competitive ratio
- experimental algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. Prentice Hall, 1993.
-
A. Ben-Tal, L. El Ghaoui, and A. S. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, 2009.
-
J. R. Birge and F. Louveaux. Introduction to Stochastic Programming. Springer Series in Operations Research. Springer, 1997.
-
A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
- T. Erlebach and M. Hoffmann. Minimum spanning tree verification under uncertainty. In Proceedings of WG, pages 164-175, 2014. URL: http://dx.doi.org/10.1007/978-3-319-12340-0_14.
-
T. Erlebach and M. Hoffmann. Query-competitive algorithms for computing with uncertainty. Bulletin of the EATCS, Vol. 116, 2015.
- T. Erlebach, M. Hoffmann, and F. Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Th. Comp. Sci., 613:51-64, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.11.025.
- T. Erlebach, M. Hoffmann, D. Krizanc, M. Mihalák, and R. Raman. Computing minimum spanning trees with uncertainty. In Proceedings of STACS, pages 277-288, 2008. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1358.
- T. Feder, R. Motwani, L. O'Callaghan, C. Olston, and R. Panigrahy. Computing shortest paths with uncertainty. Journal of Algorithms, 62:1-18, 2007. URL: http://dx.doi.org/10.1016/j.jalgor.2004.07.005.
- T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom. Computing the median with uncertainty. SIAM Journal on Computing, 32:538-547, 2003. URL: http://dx.doi.org/10.1137/S0097539701395668.
-
J. Focke. Comparative analysis of algorithms for minimum spanning tree under uncertainty. Master’s thesis, Technische Universität Berlin, 2017.
- M. Goerigk, M. Gupta, J. Ide, A. Schöbel, and S. Sen. The robust knapsack problem with queries. Computers & OR, 55:12-22, 2015. URL: http://dx.doi.org/10.1016/j.cor.2014.09.010.
- M. Gupta, Y. Sabharwal, and S. Sen. The update complexity of selection and related problems. Theory Comput. Syst., 59(1):112-132, 2016. URL: http://dx.doi.org/10.1007/s00224-015-9664-y.
- S. Kahan. A model for data in motion. In Proceedings of STOC, pages 267-277, 1991. URL: http://dx.doi.org/10.1145/103418.103449.
-
N. Megow, J. Meißner, and M. Skutella. Randomization helps computing a minimum spanning tree under uncertainty. Journal on Scientific Computing, 2017.
- G. Reinelt. TSPLIB - A traveling salesman problem library. ORSA Journal on Computing, 3(4):376-384, 1991. URL: http://dx.doi.org/10.1287/ijoc.3.4.376.