Shortest paths with a cost constraint: a probabilistic analysis (Q2043355): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 20:23, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shortest paths with a cost constraint: a probabilistic analysis |
scientific article |
Statements
Shortest paths with a cost constraint: a probabilistic analysis (English)
0 references
2 August 2021
0 references
This article starts from the concept of complete graph \(K_n\) and its set of edges. Let us given an independent random edge \(e\) having the length \(w(e)\) and random costs \(c(e)\). Having given a budget \(c(0)\), we have to find a path \(P\) from vertex 1 to vertex 2 of minimum length \(l(P)\) and the total cost \(c(P)\) less than \(c(0)\) if \(P\) denotes the set of paths from 1 to 2 in \(K_n\). This approach is a well-studied problem, at least in the worst-case. In this paper, the case is considered where \(w(e)\), \(c(e)\), are independent random variables and let \(L_n\) denote the random minimum length of a budget shortest path, \(H_n\) denote the hop-count (number of edges) in the shortest path. The authors assume that \(w(e)\), \(c(e)\) are independent copies of the uniform \([0, 1]\) random variable \(U\). In the first setting of this paper, they establish an asymptotically correct estimate of \(L_n\). The outlines of the article are: an estimate of \(L_n\) in two distinct ways, a lower bound of \(L_n\) and using Lagrangian duality, another bound is obtained. The final consideration of the authors is that the duality gap between the maximum dual value and the optimal value of the solution to the constrained shortest path problem is within \(o(1)\) of the optimal value to the latter problem.
0 references
random shortest path
0 references
cost constraint
0 references
weighted graph
0 references