Curve approximation and constrained shortest path problems
Geir Vaaland Dahl, Bjørnar Realfsen · NORA - Norwegian Open Research Archives · 1996
We study the following problem k-constrained shortest path problem: given an acyclic directed graph D = (V, E) with arc weights c_i,j, (i, j) ∈ E, two nodes s and t and an integer k, find a shortest st-path containing at most k arcs. An important application of the problem in linear curve approximation is discussed. Vertices and edges of associated polytopes are determined, and integrality of these polytopes for certain graphs are shown. We present a combinatorial algorithm for solving the problem and compare it to other methods based on Lagrangian relaxation and dynamic programming. Numerical results for curve approximation problems are reported.