A simple efficient approximation scheme for the restricted shortest path problem
Introduction
The restricted shortest path problem is a basic optimization problem that is both theoretically interesting and has practical applications (see for example [2]). In this problem the goal is to find the shortest path from a source node s to a target node t, among all paths that satisfy a certain criterion (a bounded delay for example, e.g. finding the minimal-cost T-path2). The problem is known to be -complete and has a fully polynomial approximation scheme, FPAS [1].
One of the main difficulties in obtaining a fully polynomial approximation scheme for this problem is the lack of easily computable lower and upper bounds. For this reason some of the approximation schemes for this problem have time complexities which depend on the values of the cost (or length) of the edges. Warburton [6] was the first to derive a polynomial approximation scheme for this problem on acyclic graphs. His result was improved by Hassin who gave a fully polynomial approximation scheme with time complexity of [1].
The main contribution of this paper is identifying a fairly simple and easy way to compute upper and lower bounds for this problem. The idea is to find a value cj such that if we restrict our graph G to have only edges with cost cj or smaller, it will still have a T-path, but if we delete all the edges with cost cj then the resulting graph will no longer have a T-path. We then use cj and ncj as the lower and upper bounds on the optimal solution, and derive a FPAS with time complexity of . We further improve this complexity by observing that all but the last iteration of this algorithm can work with ε=1, thus the overall complexity is reduced to . In fact we present a new test procedure which modifies the one used by Hassin. This procedure can be applied without any additional complexity increase to general graphs, even if some of the cost values associated with the edges equal zero.
Our techniques also apply to other approximation schemes for this problem. For example, Cynthia Phillips [4] provides a Polynomial Approximation Scheme,3 which applies to general graphs, with time complexity of . Using our methods, it can be converted into a FPAS with time complexity of . This is slightly worse than what we achieve using the Hassin based scheme. On the other hand, Phillips’ scheme, which uses Dijkstra's algorithm in an expanded network, is a more intuitive approximation (especially for graphs which contain cycles).
In the next section, we formally define the problem and summarize Hassin's results [1]. Then in Section 3 we describe our new approximation scheme and prove its time complexity.
Section snippets
Problem definition and Hassin's results
We use the definition from Hassin's paper [1]. The restricted shortest path problem is defined as follows. Definition 1 Let G=(V,E) be a graph with |V|=n and |E|=m, such that each edge e∈E is associated with a length (sometimes called cost) ce and a transition time (sometimes called delay) de. Let T be a positive integer, and s,t∈V be the source and target nodes. The restricted shortest path problem is to find a path in G from s to t such that the transition time (delay) along this path is no greater than T
Main results
In this section we describe our new approximation scheme. First we observe that the time complexity of Theorem 1 can be improved to . Then we find an upper and a lower bound for the optimal solution such that the ratio between them is n. Combining these two results we get the claimed improved complexity. In order to explain how to improve Hassin's algorithm we have to get into more details. Definition 2 Given an instance of the restricted shortest path problem, an approximation factor
Discussion
The main contribution of this paper is the introduction of new techniques that both improve the complexity, and enlarge the scope of the approximation scheme for the restricted shortest path problem. These techniques can be applied to other problems with similar characterizations. For example, as was already noted in [3], Hassin's techniques could be used to improve the approximation scheme for the capacitated plant allocation problem. Another area for which these results can be applied is QoS
References (6)
Approximation schemes for the restricted shortest path problem
Math. Oper. Res.
(1992)- et al.
QoS routing on networks with uncertain parameters
IEEE/ACM Trans. Networking
(1998) - et al.
Errata and comments on “approximation algorithms for the capacitated plant allocation problem”
Oper. Res. Lett.
(1996)
Cited by (237)
Online learning for route planning with on-time arrival reliability
2023, Operations Research LettersDeploying near-optimal delay-constrained paths with Segment Routing in massive-scale networks
2022, Computer NetworksCitation Excerpt :This can be performed either directly, by scaling and rounding the weights of each link, or indirectly, by dividing the solution space into intervals and only maintaining paths belonging to different intervals (Interval partitioning) [44]. Scaling methods usually consider either a high-level dynamic programming scheme or a low-level practical Dijkstra/Bellman-Ford core with pseudo-polynomial complexity, and round the link costs to turn their algorithms into an FPTAS (see for example Hassin [45], Ergun et al. [46] or Lorenz and Raz [47] methods). Goel et al. [48], in particular, chose to round the delay instead of the cost and can consider multiple destinations (as our own algorithm).
Approximation Algorithms for Directed Weighted Spanners
2023, Leibniz International Proceedings in Informatics, LIPIcsStateful Serverless Application Placement in MEC with Function and State Dependencies
2023, IEEE Transactions on ComputersEfficient Distributed DNNs in the Mobile-Edge-Cloud Continuum
2023, IEEE/ACM Transactions on Networking
- 1
Work done while visiting Bell-Labs, Lucent Technologies, and supported in part by DIMACS.