UNI-MB - logo
UMNIK - logo
 
E-viri
Celotno besedilo
Recenzirano
  • The restricted inverse opti...
    Zhang, Qiao; Guan, Xiucui; Jia, Junhua; Qian, Xinqiang; Pardalos, Panos M

    Journal of global optimization, 05/2023, Letnik: 86, Številka: 1
    Journal Article

    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.