Abstract
Given an edge weighted graph, and an acyclic edge set, the goal of the partial inverse maximum spanning tree problem is to modify the weight function as small as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the weighted \(l_{\infty }\)-norm. By studying the properties of the optimal value and a special kind of optimal solutions, combining the algorithm for the decision version of this problem with the Binary search method, we present a strongly polynomial-time algorithm for calculating the optimal value and an optimal solution.
Supported by National Numerical Windtunnel Project (No. NNW2019ZT5-B16), National Natural Science Foundation of China (Nos. 11771013, 11871256, 12071194, U20A2068), and the Basic Research Project of Qinghai (No. 2021-ZJ-703), Zhejiang Provincial Natural Science Foundation of China (No. LD19A010001).
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
References
Ben-Ayed, O., Blair, C.E.: Computational difficulties of bilevel linear programming. Oper. Res. 38(3), 556–560 (1990)
Chvátal, V.: Correction to: a De Bruijn-Erdős theorem in graphs? In: Gera, R., Haynes, T.W., Hedetniemi, S.T. (eds.) Graph Theory. PBM, pp. C1–C2. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-97686-0_15
Cai, M.-C., Duin, C.W., Yang, X., Zhang, J.: The partial inverse minimum spanning tree problem when weight increasing is forbidden. Eur. J. Oper. Res. 188, 348–353 (2008)
Gassner, E.: The partial inverse minimum cut problem with \(L_1\)-norm is strongly NP-hard. RAIRO Oper. Res. 44, 241–249 (2010)
Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13, 1194–1217 (1992)
Lai, T., Orlin, J.: The Complexity of Preprocessing. Research Report of Sloan School of Management. MIT (2003)
Li, S., Zhang, Z., Lai, H.-J.: Algorithms for constraint partial inverse matroid problem with weight increase forbidden. Theor. Comput. Sci. 640, 119–124 (2016)
Li, X., Shu, X., Huang, H., Bai, J.: Capacitated partial inverse maximum spanning tree under the weighted Hamming distance. J. Comb. Optim. 38(4), 1005–1018 (2019). https://doi.org/10.1007/s10878-019-00433-x
Li, X., Zhang, Z., Du, D.-Z.: Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm. J. Glob. Optim. 70(3), 677–685 (2017). https://doi.org/10.1007/s10898-017-0554-5
Li, X., Zhang, Z., Yang, R., Zhang, H., Du, D.-Z.: Approximation algorithms for capacitated partial inverse maximum spanning tree problem. J. Glob. Optim. 77(2), 319–340 (2019). https://doi.org/10.1007/s10898-019-00852-4
Yang, X.: Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO Oper. Res. 35, 117–126 (2001)
Yang, X., Zhang, J.: Partial inverse assignment problem under \(l_1\) norm. Oper. Res. Lett. 35, 23–28 (2007)
Yang, X., Zhang, J.: Inverse sorting problem by minimizing the total weighted number of changers and partial inverse sorting problem. Comput. Optim. Appl. 36(1), 55–66 (2007)
Zhang, Z., Li, S., Lai, H.-J., Du, D.-Z.: Algorithms for the partial inverse matroid problem in which weights can only be increased. J. Glob. Optim. 65(4), 801–811 (2016). https://doi.org/10.1007/s10898-016-0412-x
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, X., Yang, R., Zhang, H., Zhang, Z. (2021). Capacitated Partial Inverse Maximum Spanning Tree Under the Weighted \(l_{\infty }\)-norm. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-92681-6_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92680-9
Online ISBN: 978-3-030-92681-6
eBook Packages: Computer ScienceComputer Science (R0)