中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 3: 44 - 56

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.004

The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm

Expand
  • 1. College of Science, Hohai University, Nanjing 210098, Jiangsu, China
    2. School of Mathematics, Southeast University, Nanjing 210096, Jiangsu, China

Received date: 2021-11-23

  Online published: 2022-09-07

Fold

Abstract

We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm.

Key words： minimum spanning tree; $l_\infty$ norm; inverse optimal value problem; strongly polynomial time algorithm

Cite this article

Binwu ZHANG, Xiucui GUAN . The bounded inverse optimal value problem on minimum spanning tree under unit infinity norm[J]. Operations Research Transactions, 2022 , 26(3) : 44 -56 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.004

References

1 BurtonD,TointP.On an instance of the inverse shortest path problem[J].Mathematical Programming,1992,53(1):45-61.
2 AhujaR K,OrlinJ B.A faster algorithm for the inverse spanning tree problem[J].Journal of Algorithms,2000,34(1):177-193.
3 GuanX C,HeX Y,PardalosP M,et al.Inverse max+sum spanning tree problem under hamming distance by modifying the sum-cost vector[J].Journal of Global Optimization,2017,69(4):911-925.
4 GuanX C,PardalosP M,ZhangB W.Inverse max+sum spanning tree problem under weighted $l_1$-norm by modifying the sum-cost vector[J].Optimization Letters,2018,12(5):1065-1077.
5 HeY,ZhangB W,YaoE Y.Weighted inverse minimum spanning tree problems under Hamming distance[J].Journal of Combinatorial optimization,2005,9(1):91-100.
6 HochbaumD S.Efficient algorithms for the inverse spanning tree problem[J].Operations Research,2003,51(5):785-797.
7 LiX Y,ZhangZ,DuD Z.Partial inverse maximum spanning tree in which weight can only be decreased under $l_p$-norm[J].Journal of Global Optimization,2018,70(3):677-685.
8 LiuL C,YaoE Y.Inverse min-max spanning tree problem under the weighted sum-type Hamming distance[J].Theoretical Computer Science,2008,396(s 1-3):28-34.
9 SokkalingamP T,AhujaR K,OrlinJ B.Solving inverse spanning tree problems through network flow techniques[J].Operational Research,1999,47(2):291-298.
10 ZhangB W,GuanX C,WangQ,et al.The complexity analysis of the shortest path improvement problem under the hamming distance[J].Pacific Journal of Optimization,2015,11(4):605-618.
11 ZhangB W,GuanX C,PardalosP M,et al.An algorithm for the shortest path improvement problem on rooted trees under the unit Hamming distance[J].Journal of Optimization Theory & Applications,2018,178(2):538-559.
12 ZhangB W,ZhangJ Z,QiL Q.The shortest path improvement problem under Hamming distance[J].Journal of Combinatorial Optimization,2006,12(4):351-361.
13 ZhangB W,ZhangJ Z,HeY.The center location improvement problem under Hamming distance[J].Journal of Combinatorial optimization,2005,9(2):187-198.
14 ZhangJ Z,XuS J,MaZ F.An algorithm for inverse minimum spanning tree problem[J].Optimization Method & Software,1997,8(1):69-84.
15 ZhangB W,ZhangJ Z,HeY.Constrained inverse minimum spanning tree problems under bottleneck-type Hamming distance[J].Journal of Global Optimization,2006,34,467-474.
16 AhmedS,GuanY P.The inverse optimal value problem[J].Mathematical Programming,2005,102(1):91-110.
17 LvY B,HuaT S,WanZ P.A penalty function method for solving inverse optimal value problem[J].Journal of Computational and Applied Mathematics,2008,220(12):175-180.
18 ZhangB W,GuanX C,ZhangQ.Inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm[J].Optimization Letters,2020,14(8):2301-2322.
19 ZhangB W,GuanX C,PardalosP M,et al.The lower bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm[J].Journal of Global Optimization,2021,79(3):757-777.
20 AhujaR K,MagnantiT L,OrlinJ B.Network Flows, Theory, Algorithms, and Applications[M].New Jersey:Prentice Hall,1993.
Options
Outlines

/

〈 〉