The Restricted Inverse Optimal Value Problem under Weighted Bottle-neck Hamming distance on trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910771996262400 |
|---|---|
| author | Zhang, Qiao Li, Xiao Guan, Xiucui |
| author_facet | Zhang, Qiao Li, Xiao Guan, Xiucui |
| contents | We consider the Restricted Inverse Optimal Value Problem (RIOVSP) on trees under weighted bottleneck Hamming distance, denoted as (RIOVSPT$_{BH}$). The problem aims to minimize the total cost under weighted bottle-neck Hamming distance such that the length of the shortest root-leaf path of the tree is lower-bounded by a given value by adjusting the length of some edges. Additionally, the specified lower bound must correspond to the length of a particular root-leaf path. Through careful analysis of the problem's structural properties, we develop an algorithm with $O(n\log n)$ time complexity to solve (RIOVSPT$_{BH}$). Furthermore, by removing the path-length constraint, we derive the Minimum Cost Shortest Path Interdiction Problem on Trees (MCSPIT), for which we present an $O(n\log n)$ time algorithm that operates under weighted bottleneck Hamming distance. Extensive computational experiments demonstrate the efficiency and effectiveness of both algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20703 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Restricted Inverse Optimal Value Problem under Weighted Bottle-neck Hamming distance on trees Zhang, Qiao Li, Xiao Guan, Xiucui Data Structures and Algorithms Optimization and Control We consider the Restricted Inverse Optimal Value Problem (RIOVSP) on trees under weighted bottleneck Hamming distance, denoted as (RIOVSPT$_{BH}$). The problem aims to minimize the total cost under weighted bottle-neck Hamming distance such that the length of the shortest root-leaf path of the tree is lower-bounded by a given value by adjusting the length of some edges. Additionally, the specified lower bound must correspond to the length of a particular root-leaf path. Through careful analysis of the problem's structural properties, we develop an algorithm with $O(n\log n)$ time complexity to solve (RIOVSPT$_{BH}$). Furthermore, by removing the path-length constraint, we derive the Minimum Cost Shortest Path Interdiction Problem on Trees (MCSPIT), for which we present an $O(n\log n)$ time algorithm that operates under weighted bottleneck Hamming distance. Extensive computational experiments demonstrate the efficiency and effectiveness of both algorithms. |
| title | The Restricted Inverse Optimal Value Problem under Weighted Bottle-neck Hamming distance on trees |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2412.20703 |