Partial inverse min–max spanning tree problem under the weighted bottleneck hamming distance
Tóm tắt
Từ khóa
Tài liệu tham khảo
Ahuja RK, Orlin JB (2000) A faster algorithm for the inverse spanning tree problem. J Algorithms 34:177–193
Ben-Ayed O, Blair CE (1990) Computational difficulties of bilevel linear programming. Oper Res 38(3):556–560
Cai M-C, Duin CW, Yang X, Zhang J (2008) The partial inverse minimum spanning tree problem when weight increasing is forbidden. Eur J Oper Res 188:348–353
Camerini PM (1978) The min–max spanning tree problem and some extensions. Inf Process Lett 7(1):10–14
Gassner E (2010) The partial inverse minimum cut problem with $$L_1$$-norm is strongly NP-hard. RAIRO Oper Res 44:241–249
Guan X, He X, Pardalos PM, Zhang B (2017) Inverse max+sum spanning tree problem under Hamming distance by modifying the sum-cost vector. J Global Optim 69(4):911–925
Guan X, Pardalos PM, Zhang B (2018) Inverse max+sum spanning tree problem under weighted $$l_1$$ norm by modifying the sum-cost vector. Optim Lett 12(5):1065–1077
Guan X, Pardalos PM, Zuo X (2015) Inverse Max+Sum spanning tree problem by modifying the sum-cost vector under weighted $$l_\infty $$ Norm. J Global Optim 61(1):165–182
Guan X, Zhang J (2007) Inverse constrained bottleneck problems under weighted $$l_\infty $$ norm. Comput Oper Res 34:3243–3254
Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13:1194–1217
He Y, Zhang B, Yao E (2005) Weighted inverse minimum spanning tree problems under hamming distance. J Comb Optim 9:91–100
Hochbaum DS (2003) Efficient algorithms for the inverse spanning-tree problem. Oper Res 51(5):785–797
Lai T, Orlin J (2003) The complexity of preprocessing. Research Report of Sloan School of Management. MIT, Cambridge
Li S, Zhang Z, Lai H-J (2016) Algorithms for constraint partial inverse matroid problem with weight increase forbidden. Theoret Comput Sci 640:119–124
Li X, Shu X, Huang H, Bai J (2019) Capacitated partial inverse maximum spanning tree under the weighted Hamming distance. J Comb Optim 38:1005–1018
Li X, Zhang Z, Du D-Z (2018) Partial inverse maximum spanning tree in which weight can only be decreased under $$l_p$$-norm. J Global Optim 30:677–685
Li X, Zhang Z, Yang R, Zhang H, Du D-Z (2020) Approximation algorithms for capacitated partial inverse maximum spanning tree problem. J Global Optim 77(2):319–340
Liu L, Wang Q (2009) Constrained inverse min-max spanning tree problems under the weighted Hamming distance. J Global Optim 43:83–95
Liu L, Yao E (2008) Inverse min-max spanning tree problem under the Weighted sum-type Hamming distance. Theoret Comput Sci 196:28–34
Sokkalingam PT, Ahuja RK, Orlin JB (1999) Solving inverse spanning tree problems through network flow techniques. Oper Res 47:291–298
Tayyebi J, Sepasian AR (2020) Partial inverse min-max spanning tree problem. J Comb Optim 40:1075–1091
Wang H, Guan X, Zhang Q, Zhang B (2021) Capacitated inverse optimal value problem on minimum spanning tree under bottleneck Hamming distance. J Comb Optim 41:861–887
Yang X (2001) Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO Oper Res 35:117–126
Yang X, Zhang J (2007) Partial inverse assignment problem under $$l_1$$ norm. Oper Res Lett 35:23–28
Yang X, Zhang J (2007) Inverse sorting problem by minimizing the total weighted number of changers and partial inverse sorting problem. Comput Optim Appl 36(1):55–66
Yang X, Zhang J (2007) Some inverse min-max network problems under weighted $$l_1$$ and $$l_{\infty }$$ norms with bound constraints on changes. J Comb Optim 13(2):123–135
Zhang B, Guan X, Zhang Q (2020) Inverse optimal value problem on minimum spanning tree under unit $$l_{\infty }$$-norm. Optim Lett 14(8):2301–2322
Zhang B, Zhang J, He Y (2006) Constrained inverse minimum spanning tree problems under the bottleneck-type Hamming distance. J Global Optim 34:467–474
Zhang J, Xu S, Ma Z (1997) An algorithm for inverse minimum spanning tree problem. Optim Methods Softw 8(1):69–84