The Restricted Inverse Optimal Value Problem on Shortest Path under l_∞ Norm on Trees

Abstract

We study the restricted inverse optimal value problem on shortest paths under the weighted l_∞ norm on trees (RIOVSPT_∞): adjust edge weights at minimum worst-link cost so that the shortest root--leaf path is lower-bounded by a given value D, a restriction on a prescribed path P₀. Unlike the l₁ version minimizing total adjustment cost, the l_∞ objective controls the worst link, the criterion relevant in bandwidth pricing. We characterize feasibility through the minimum cost shortest path interdiction problem (MCSPIT_∞), whose optimal solution ŵ splits the instance at the first edge of P₀ into two independent subproblems. Relative to ŵ, three cases arise. The first two admit closed-form optimal solutions. The third reduces to a parametric subproblem SPIT⁰_∞(M): minimize the length of P₀ on the gate subtree under the budget C(ŵ)+M with all other root--leaf paths kept at least D. It is solved exactly by an iterative greedy procedure. On its value function V(M), the predicate V(M)≤ D is equivalent to the nonnegativity of truncated-bound margins, which are monotone, continuous and piecewise affine; the smallest such M gives the optimal value, located by binary search over the edge-bound breakpoints with an exact affine threshold evaluation. The same margin test on the full tree gives a uniform algorithm for all cases. Both algorithms run in O(nlog n) time. Experiments on synthetic trees agree with a linear programming baseline and illustrate the two algorithms' distinct runtime profiles.

On a Special Inverse Singular Value Problem for Certain Classes of Hessenberg Matrices
Hubert Pickmann-Soto, Hans Nina, Susana Arela-Pérez +1
Mathematics13 Oct 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Water Transport on 3-Spiders: Unbounded Lengths of Shortest Optimal Strategies
Guanheng Chen, Ran Tao, Tianyi Tao
arXiv22 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Infinite Families of Counterexamples to a Conjecture of Liu and Qian and a Refined Inverse Theorem for Restricted Sumsets in ℤ_p
Jiantao Li, Xinyi Liang
arXiv11 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
A coupling normal form for reversible center-center Hamiltonians with application to the restricted three-body problem
Mingpei Lin
arXiv20 Oct 2026PreprintarXiv licenceFull textDynamical systemsarXiv
Marchal-type lemmas for the restricted (N+1)-body problem with their applications
Kuo-chang Chen, Guowei Yu
arXiv27 Oct 2026PreprintarXiv licenceFull textDynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026restricted,
  title = {{The Restricted Inverse Optimal Value Problem on Shortest Path under $l_\infty$ Norm on Trees}},
  author = {Qiao Zhang and Ying Wang and Xiao Li and Junhua Jia and Xiucui Guan and Panos M. Pardalos},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23710},
  eprint = {2610.23710},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23710},
}

RIS

TY  - UNPB
TI  - The Restricted Inverse Optimal Value Problem on Shortest Path under l_∞ Norm on Trees
AU  - Qiao Zhang
AU  - Ying Wang
AU  - Xiao Li
AU  - Junhua Jia
AU  - Xiucui Guan
AU  - Panos M. Pardalos
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23710
UR  - https://arxiv.org/abs/2610.23710
AB  - We study the restricted inverse optimal value problem on shortest paths under the weighted l_∞ norm on trees (RIOVSPT_∞): adjust edge weights at minimum worst-link cost so that the shortest root--leaf path is lower-bounded by a given value D, a restriction on a prescribed path P_0. Unlike the l_1 version minimizing total adjustment cost, the l_∞ objective controls the worst link, the criterion relevant in bandwidth pricing. We characterize feasibility through the minimum cost shortest path interdiction problem (MCSPIT_∞), whose optimal solution ŵ splits the instance at the first edge of P_0 into two independent subproblems. Relative to ŵ, three cases arise. The first two admit closed-form optimal solutions. The third reduces to a parametric subproblem SPIT^0_∞(M): minimize the length of P_0 on the gate subtree under the budget C(ŵ)+M with all other root--leaf paths kept at least D. It is solved exactly by an iterative greedy procedure. On its value function V(M), the predicate V(M)≤ D is equivalent to the nonnegativity of truncated-bound margins, which are monotone, continuous and piecewise affine; the smallest such M gives the optimal value, located by binary search over the edge-bound breakpoints with an exact affine threshold evaluation. The same margin test on the full tree gives a uniform algorithm for all cases. Both algorithms run in O(nlog n) time. Experiments on synthetic trees agree with a linear programming baseline and illustrate the two algorithms' distinct runtime profiles.
ER  -

Abstract

Related

Cite