Restricted Inverse Optimal Value Problem on Minimum Spanning Tree

In this chapter, we address the restricted inverse optimal value problem on minimum spanning tree under various norms. Under the weighted l ∞ $$l_{\infty }$$ norm with bounds, we establish optimality conditions and develop two efficient algorithms operating in O ( m 2 n ) $$O(m^2n)$$ and O ( m 2 log n ) $$O(m^2\log n)$$ , where m and n $$m\ \mbox{and}\ n$$ are the number of edges and nodes of a graph G. Additionally, an O ( mn ) $$O(mn)$$ algorithm is introduced for the (RIOVMST ∞ $${ }_\infty $$ ) problem with unit norm and bounds. For the l 1 $$l_1$$ norm case, we formulate the problem as a linear program, derive a dual subproblem, and calculate a critical value z ∗ $$z^*$$ using binary search, ultimately solving the problem with a complexity of O ( m 2 n 2 log n log ( nC ) ) $$O(m^2n^2\log n\log (nC))$$ . Under the bottleneck Hamming distance, three binary search algorithms are developed with a uniform time complexity of O ( mn log n ) $$O(mn\log n)$$ . An open problem is posed regarding a strongly polynomial time algorithm for the (RIOVMST 1 $$_1$$ ) problem.