Equivalence, Unification and Generality of Two Approaches to the Constrained Shortest Path Problem with Extensions

摘要

In this paper we first show that the heuristics presented in [4] and [11] are equivalent. Thus the LARAC algorithm of, though originally intended for the constrained shortest path problem, is general enough and is applicable to the general class of optimization problems considered in [11]. As pointed out by one of the authors of, we provide further evidence of the generality of LARAC by proving the claims (in particular, the optimality criterion) on which LARAC is based, without involving the properties of shortest paths. LARAC terminates with two paths p_c and p_d We show that these two paths solve a minimization problem involving a flow variable. We also establish a few new properties on the solutions obtained by LARAC. We present a new heuristic called LARAC-BIN based on binary search. The new heuristic involves a parameter whose value can be specified in advance depending on the allowable deviation of the cost of the path produced by the heuristic from the optimum value. We conclude by pointing out how LARAC and LARAC-BIN can be used in conjunction with ε-approximation techniques to generate paths whose costs are guaranteed to be within certain factor of the optimum. These heuristics will play a major role as building blocks in designing heuristic/approximation techniques for general classes of combinatorial optimization problems.