Details

Autor(en) / Beteiligte

• Zhang, Qiao
• Guan, Xiucui
• Jia, Junhua
• Qian, Xinqiang
• Pardalos, Panos M

Titel

The restricted inverse optimal value problem on shortest path under [Formula omitted] norm on trees

Ist Teil von

• Journal of global optimization, 2023-05, Vol.86 (1), p.251

Ort / Verlag

Springer

Erscheinungsjahr

2023

Quelle

SpringerLink

Beschreibungen/Notizen

• We consider the restricted inverse optimal value problem on shortest path under weighted [Formula omitted] norm on trees (RIOVSPT [Formula omitted]). It aims at adjusting some edge weights to minimize the total cost under weighted [Formula omitted] norm on the premise that the length of the shortest root-leaf path of the tree is lower-bounded by a given value D, which is just the restriction on the length of a given root-leaf path [Formula omitted]. If we ignore the restriction on the path [Formula omitted], then we obtain the minimum cost shortest path interdiction problem on trees (MCSPIT [Formula omitted]). We analyze some properties of the problem (RIOVSPT [Formula omitted]) and explore the relationship of the optimal solutions between (MCSPIT [Formula omitted]) and (RIOVSPT [Formula omitted]). We first take the optimal solution of the problem (MCSPIT [Formula omitted]) as an initial infeasible solution of problem (RIOVSPT [Formula omitted]). Then we consider a slack problem [Formula omitted], where the length of the path [Formula omitted] is greater than D. We obtain its feasible solutions gradually approaching to an optimal solution of the problem (RIOVSPT [Formula omitted]) by solving a series of subproblems [Formula omitted]. It aims at determining the only weight-decreasing edge on the path [Formula omitted] with the minimum cost so that the length of the shortest root-leaf path is no less than D. The subproblem can be solved by searching for a minimum cost cut in O(n) time. The iterations continue until the length of the path [Formula omitted] equals D. Consequently, the time complexity of the algorithm is [Formula omitted] and we present some numerical experiments to show the efficiency of the algorithm. Additionally, we devise a linear time algorithm for the problem (RIOVSPT [Formula omitted]) under unit [Formula omitted] norm.