Abstract
Many works within robust combinatorial optimisation consider interval-valued costs or constraints. While most of these works focus on finding unique solutions such as minimax ones, a few consider the problem of characterising a set of non-dominated optimal solutions. This paper is situated within this line of work, and consider the problem of exactly enumerating the set of non-dominated spanning trees under interval-valued costs. We show in particular that each tree in this set can be obtained through a polynomial procedure, and provide an efficient algorithm to achieve the enumeration.
Due to paucity of space, proofs has been omitted. The full version is available here: https://hal.utc.fr/hal-04155185.
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
Similar content being viewed by others
Notes
- 1.
We have provided proofs in the appendix for review purposes, as including them would exceed page limits. Appendices will not be part of the final version.
References
Aron, I.D., Van Hentenryck, P.: On the complexity of the robust spanning tree problem with interval data. Oper. Res. Lett. 32(1), 36–40 (2004)
Benabbou, N., Perny, P.: On possibly optimal tradeoffs in multicriteria spanning tree problems. In: Walsh, T. (ed.) ADT 2015. LNCS (LNAI), vol. 9346, pp. 322–337. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23114-3_20
Destercke, S., Guillaume, R.: Necessary and Possibly Optimal Items in Selecting Problems. In: Ciucci, D., et al. (eds.) IPMU 2022, Part I. Communications in Computer and Information Science, vol. 1601, pp. 494–503. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-08971-8_41
Guillaume, R., Kasperski, A., Zieliński, P.: Distributionally robust possibilistic optimization problems. Fuzzy Sets Syst. 454, 56–73 (2023)
Hradovich, M., Kasperski, A., Zielinski, P.: The recoverable robust spanning tree problem with interval costs is polynomially solvable. Optimiz. Lett. 11(1), 17–30 (2017)
Kasperski, A.: Discrete Optimization with Interval Data. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-78484-5.pdf
Kozina, G.L., Perepelitsa, V.A.: Interval spanning trees problem: solvability and computational complexity. Interval Comput. 1(1), 42–50 (1994)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)
Montemanni, R., Gambardella, L.M.: A branch and bound algorithm for the robust spanning tree problem with interval data. Eur. J. Oper. Res. 161(3), 771–779 (2005)
Pop, P.C.: The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances. Eur. J. Oper. Res. 283(1), 1–15 (2020)
Quaeghebeur, E., Shariatmadar, K., De Cooman, G.: Constrained optimization problems under uncertainty with coherent lower previsions. Fuzzy Sets Syst. 206, 74–88 (2012)
Vu, T.A., Afifi, S., Lefèvre, É., Pichon, F.: On modelling and solving the shortest path problem with evidential weights. In: Le H’egarat-Mascle, S., Bloch, I., Aldea, E. (eds.) BELIEF 2022. LNCS, vol. 13506, pp. 139–149. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-17801-6_14
Yaman, H., Karaş, O.E., Pınar, M.Ç.: The robust spanning tree problem with interval data. Oper. Res. Lett. 29(1), 31–40 (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Davot, T., Destercke, S., Savourey, D. (2024). On the Enumeration of Non-dominated Spanning Trees with Imprecise Weights. In: Bouraoui, Z., Vesic, S. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2023. Lecture Notes in Computer Science(), vol 14294. Springer, Cham. https://doi.org/10.1007/978-3-031-45608-4_26
Download citation
DOI: https://doi.org/10.1007/978-3-031-45608-4_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-45607-7
Online ISBN: 978-3-031-45608-4
eBook Packages: Computer ScienceComputer Science (R0)