Inverse Max+Sum Spanning Tree Problems

In this chapter, the inverse max+sum spanning tree problem, a novel class of inverse optimization problems with combined minimax-minsum objectives, has been thoroughly examined. By focusing on the modification of the sum-cost vector under both weighted l 1 $$l_1$$ and l ∞ $$l_\infty $$ norms, as well as under weighted Hamming distance, we have developed mathematical models and efficient algorithms. The l 1 $$l_1$$ norm problem has been transformed into a linear programming problem, addressed with a column generation algorithm, revealing a fascinating connection to the max+sum spanning tree problem, solvable in O ( m log n ) $$O(m \log n)$$ time. The l ∞ $$l_\infty $$ norm problem has been proven to be a linear fractional combinatorial optimization problem, tackled with a discrete Newton method within O ( m 2 log m ) $$O(m^2 \log m)$$ iterations. For the Hamming distance, a binary search algorithm has been designed for the bottleneck case with a complexity of O ( m log 2 n ) $$O(m \log ^2 n)$$ , while the sum case has been identified as NP-hard. Modifying the max weight vector under the l ∞ $$l_\infty $$ norm led to a strongly polynomial time algorithm with a runtime of O ( m 2 log n ) $$O(m^2 \log n)$$ .