Paper Info
Title
Inverse max plus sum spanning tree problem under weighted l(infinity) norm by modifying max-weight vector
Abstract
The max+sum spanning tree (MSST) problem is to determine a spanning tree T whose combined weight max(e is an element of T) w(e) + Sigma(e is an element of T) c(e) is minimum for a given edge-weighted undirected network G (V, E, c, (w) over bar). This problem can be solved within O(m log n) time, where m and n are the numbers of edges and nodes, respectively. An inverse MSST problem (EMSST) aims to determine a new weight vector (w) over bar so that a given T-0 becomes an optimal MSST of the new network G(V, E, c, (w) over bar). The EMSST problem under weighted l(infinity) norm is to minimize the modification cost max(e is an element of E) q(e)vertical bar(w) over bar (e) - w(e)vertical bar, where q(e) is a cost modifying the weight w(e). We first provide some optimality conditions of the problem. Then we propose a strongly polynomial time algorithm in O(m(2) log n) time based on a binary search and a greedy method. There are O(m) iterations and we solve an MSST problem under a new weight in each iteration. Finally, we perform some numerical experiments to show the efficiency of the algorithm.
Year
DOI
Venue
2022
10.1007/s10898-022-01170-y
JOURNAL OF GLOBAL OPTIMIZATION
Keywords
DocType
Volume
Inverse max plus sum spanning tree, Weighted l(infinity) norm, Binary search method, Strongly polynomial time algorithm
Journal
84
Issue
ISSN
Citations 
3
0925-5001
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Junhua Jia100.34
Xiucui Guan2325.85
Qiao Zhang322.43
Xinqiang Qian400.34
P. M. Pardalos526945.19