ABSTRACT
In this chapter we present an ε-approximation algorithm for the constrained shortest path (CSP) problem. Recall from Chapter 36 that the CSP problem is to determine, from among all s − t paths, a minimum cost path that has a delay less than or equal to a specified value. Also, an ε-approximation algorithm for the CSP problem constructs a path with cost c˜ such that |(c∗−c˜)|/c∗ ≤ ε for any ε > 0, where c∗ is the cost of the optimum solution. Warburton [1] was the first to develop an ε-approximation algorithm for the CSP problem when the given graph is acyclic. This result was improved later by Hassin [2] that resulted in a fully polynomial time approximation algorithm with complexity of O(mn2/ε log(n/ε)) using scaling and rounding of edge costs, a dynamic programming-based test procedure to determine if the optimum value OPT ≥ v or not for a given value of v and binary search in a logarithmic scale. Hassin first developed an approximation algorithm of complexity O((mn/ε) log log(UB/LB)) where UB and LB are valid upper and lower bounds, respectively for the optimum solution. He also showed how to refine this algorithm resulting in a fully polynomial time approximation algorithm. To achieve this Hassin used the interval partitioning technique [3] (see also Chapter 35). Subsequently Lorenz and Raz [4] achieved an algorithm which improves Hassin’s ε-approximation algorithm by a factor of n. This is done by showing how to find UB and LB such that UB/LB ≤ n. We call this improved algorithm as Hassin-Lorenz-Raz (HLR) algorithm. Through Section 37.2 the HLR algorithm is developed. We follow the treatment in Lorenz and Raz [4].
