A simple efficient approximation scheme for the restricted shortest path problem

https://doi.org/10.1016/S0167-6377(01)00069-4Get rights and content

Abstract

In this short paper we give a very simple fully polynomial approximation scheme for the restricted shortest path problem. The complexity of this ε-approximation scheme is O(|E|n(loglogn+1/ε)), which improves Hassin's original result (Math. Oper. Res. 17 (1) (1992) 36) by a factor of n. Furthermore, this complexity bound is valid for any graph, regardless of the cost values. This generalizes Hassin's results which apply only to acyclic graphs.

Our algorithm is based on Hassin's original result with two improvements. First we modify Hassin's result and achieve time complexity of O(|E|n(loglog(UB/LB)+1/ε)), where UB and LB are upper and lower bounds for the problem. This modified version can be applied to general graphs with any cost values. Then we combine it with our second contribution, which shows how to find an upper and a lower bound such that UB/LBn, to obtain the claimed result.

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 NP-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 O(|E|(n2/ε)log(n/ε)) [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 O(|E|(n/ε)loglogn)). 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 O(|E|n(loglogn+1/ε)). 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 O((|E|n/ε+(n2/ε)log(n2/ε))loglogUB/LB). Using our methods, it can be converted into a FPAS with time complexity of O((|E|n+n2logn)loglogn+|E|n/ε+(n2/ε)log(n2/ε)). 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 eE 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,tV be the source and target nodes. The restricted shortest path problem is to find a path p 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 O(mn(loglog(UB/LB)+1/ε)). 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)

  • R. Hassin

    Approximation schemes for the restricted shortest path problem

    Math. Oper. Res.

    (1992)
  • D.H. Lorenz et al.

    QoS routing on networks with uncertain parameters

    IEEE/ACM Trans. Networking

    (1998)
  • M. Labbè et al.

    Errata and comments on “approximation algorithms for the capacitated plant allocation problem”

    Oper. Res. Lett.

    (1996)
There are more references available in the full text version of this article.

Cited by (237)

  • Deploying near-optimal delay-constrained paths with Segment Routing in massive-scale networks

    2022, Computer Networks
    Citation 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, LIPIcs
  • Efficient Distributed DNNs in the Mobile-Edge-Cloud Continuum

    2023, IEEE/ACM Transactions on Networking
View all citing articles on Scopus
1

Work done while visiting Bell-Labs, Lucent Technologies, and supported in part by DIMACS.

View full text