Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.09443 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929522202378240 |
|---|---|
| author | Kaymakov, Kirill V. Malyshev, Dmitry S. |
| author_facet | Kaymakov, Kirill V. Malyshev, Dmitry S. |
| contents | The tolerance of an element of a combinatorial optimization problem with respect to a given optimal solution is the maximum change, i.e., decrease or increase, of its cost, such that this solution remains optimal. The bottleneck path problem, for given an edge-capacitated graph, a source, and a target, is to find the $\max$-$\min$ value of edge capacities on paths between the source and the target. For any given sample of this problem with $n$ vertices and $m$ edges, there is known the Ramaswamy-Orlin-Chakravarty's algorithm to compute an optimal path and all tolerances with respect to it in $O(m+n\log n)$ time. In this paper, for any in advance given $(n,m)$-network with distinct edge capacities and $k$ source-target pairs, we propose an $O\Big(m α(m,n)+\min\big((n+k)\log n,km\big)\Big)$-time preprocessing, where $α(\cdot,\cdot)$ is the inverse Ackermann function, to find in $O(k)$ time all $2k$ tolerances of an arbitrary edge with respect to some $\max\min$ paths between the paired sources and targets. To find both tolerances of all edges with respect to those optimal paths, it asymptotically improves, for some $n,m,k$, the Ramaswamy-Orlin-Chakravarty's complexity $O\big(k(m+n\log n)\big)$ up to $O(mα(n,m)+km)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09443 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem Kaymakov, Kirill V. Malyshev, Dmitry S. Data Structures and Algorithms Discrete Mathematics The tolerance of an element of a combinatorial optimization problem with respect to a given optimal solution is the maximum change, i.e., decrease or increase, of its cost, such that this solution remains optimal. The bottleneck path problem, for given an edge-capacitated graph, a source, and a target, is to find the $\max$-$\min$ value of edge capacities on paths between the source and the target. For any given sample of this problem with $n$ vertices and $m$ edges, there is known the Ramaswamy-Orlin-Chakravarty's algorithm to compute an optimal path and all tolerances with respect to it in $O(m+n\log n)$ time. In this paper, for any in advance given $(n,m)$-network with distinct edge capacities and $k$ source-target pairs, we propose an $O\Big(m α(m,n)+\min\big((n+k)\log n,km\big)\Big)$-time preprocessing, where $α(\cdot,\cdot)$ is the inverse Ackermann function, to find in $O(k)$ time all $2k$ tolerances of an arbitrary edge with respect to some $\max\min$ paths between the paired sources and targets. To find both tolerances of all edges with respect to those optimal paths, it asymptotically improves, for some $n,m,k$, the Ramaswamy-Orlin-Chakravarty's complexity $O\big(k(m+n\log n)\big)$ up to $O(mα(n,m)+km)$. |
| title | Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2408.09443 |