Abstract
We consider the problem of finding a minimum spanning tree (MST) in a graph with uncertain edge weights given by open intervals on the edges. The exact weight of an edge in the corresponding uncertainty interval can be queried at a given cost. The task is to determine a possibly adaptive query sequence of minimum total cost for finding an MST. For uniform query cost, a deterministic algorithm with best possible competitive ratio 2 is known [7].
We solve a long-standing open problem by showing that randomized query strategies can beat the best possible competitive ratio 2 of deterministic algorithms. Our randomized algorithm achieves expected competitive ratio \(1+1/\sqrt{2}\approx 1.707\). This result is based on novel structural insights to the problem enabling an interpretation as a generalized online bipartite vertex cover problem. We also consider arbitrary, edge-individual query costs and show how to obtain algorithms matching the best known competitive ratios for uniform query cost. Moreover, we give an optimal algorithm for the related problem of computing the exact weight of an MST at minimum query cost. This algorithm is based on an interesting relation between different algorithmic approaches using the cycle-property and the cut-property characterizing MSTs. Finally, we argue that all our results also hold for the more general setting of matroids. All our algorithms run in polynomial time.
This research was carried out in the framework of Matheon supported by Einstein Foundation Berlin. The first two authors were additionally supported by the German Science Foundation (DFG) under contract ME 3825/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.S.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press (2009)
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research. Springer, Heidelberg (1997)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
Erlebach, T.: Computing with uncertainty. Invited lecture, Graduate Program MDS, Berlin (2013)
Erlebach, T., Hoffmann, M.: Minimum spanning tree verification under uncertainty. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 164–175. Springer, Heidelberg (2014)
Erlebach, T., Hoffmann, M., Kammer, F.: Query-competitive algorithms for cheapest set problems under uncertainty. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 263–274. Springer, Heidelberg (2014)
Erlebach, T., Hoffmann, M., Krizanc, D., Mihalák, M., Raman, R.: Computing minimum spanning trees with uncertainty. In: Proc. STACS, pp. 277–288 (2008)
Feder, T., Motwani, R., O’Callaghan, L., Olston, C., Panigrahy, R.: Computing shortest paths with uncertainty. Journal of Algorithms 62, 1–18 (2007)
Feder, T., Motwani, R., Panigrahy, R., Olston, C., Widom, J.: Computing the median with uncertainty. SIAM Journal on Computing 32, 538–547 (2003)
Goerigk, M., Gupta, M., Ide, J., Schöbel, A., Sen, S.: The robust knapsack problem with queries. Computers & OR 55, 12–22 (2015)
Gupta, M., Sabharwal, Y., Sen, S.: The update complexity of selection and related problems. In: Proc. of FSTTCS. LIPIcs, vol. 13, pp. 325–338 (2011)
Kahan, S.: A model for data in motion. In: Proc. of STOC, pp. 267–277 (1991)
Khanna, S., Tan, W.C.: On computing functions with uncertainty. In: Proceedings of PODS, pp. 171–182 (2001)
Korte, B., Vygen, J.: Combinatorial optimization. Springer (2012)
Olston, C., Widom, J.: Offering a precision-performance tradeoff for aggregation queries over replicated data. In: Proceedings of VLDB, pp. 144–155 (2000)
Patil, P., Shrotri, A.P., Dandekar, A.R.: Management of uncertainty in supply chain. Int. J. of Emerging Technology and Advanced Engineering 2, 303–308 (2012)
Wang, Y., Wong, S.C.-W.: Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 1070–1081. Springer, Heidelberg (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Megow, N., Meißner, J., Skutella, M. (2015). Randomization Helps Computing a Minimum Spanning Tree under Uncertainty. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_73
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_73
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)