Algorithms for finding paths with multiple constraints 论文

摘要

Abstract Let G = ( V, E ) be a graph with weight function w : E rightarrow Z + and length function l : E /rightarrow Z + . The problem of determining for v 1 , V 2 /in V whether there is a path from v 1 to v 2 with weight at most W and length at most L is NP‐complete. This paper gives two approaches to meeting or approximating the length and weight constraints. The first approach is to use a pseudopolynomial‐time algorithm which determines whether a path meets the constraints. Its running time is O ( n 5 b log nb ) where n = |V| and b is the largest length or weight. If tables with O ( n 3 b ) entries are kept then all instances of multiple constraints may be decided. Table size may be substantially decreased if one is willing to tolerate incorrect answers to rare instances. The algorithm is suitable for distributed execution. In the second approach, an objective function is defined which evaluates a path's distance from meeting the constraints. Polynomial‐time algorithms attempt to find good paths in terms of the objective function. One algorithm is at most 1.62 times worst than optimal. A notion of “average worst‐case behavior” is defined. The algorithm's “average” behavior is 1.51 times worse than optimal.