Shortest paths with a cost constraint: a probabilistic analysis (Q2043355)

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.