Sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.     

Three Hoppy path problems and ternary paths

In this paper we solve several recurrence relations with two (three) indices using combinatorial methods. Moreover, we present several recurrence relations with two (three) indices related to ternary paths and k-ary paths.     

Some optimal path problems subject to improvements

In this paper, the functional equation technique of dynamic programming is applied to solve the problems of a) determining an optimal path from a given origin to a fixed destination when the path is subject to a given number of improvements, b) finding an optimal path from a given origin to an assigned destination by passing at least once through each node of a set of specified nodes when the path is subject to a given number of improvements, c) obtaining an optimal path from a given origin to a fixed destination by passing at least once through at least one node of each ofK sets of specified nodes when the path is subject to a given number of improvements.

---

Zusammenfassung In dieser Arbeit wird die Funktionalgleichung des dynamischen Programmierens verwendet, um folgende drei Netzwerkprobleme zu lösen: a) Bestimmung eines optimalen Pfades von einem gegebenen Anfangs- zu einem gegebenen Endknoten, wenn längs einem Pfad eine gewisse Anzahl von Verbesserungen möglich sind. b) Wie a), wobei zusätzlich der Pfad mindestens einmal durch jeden Knoten einer spezifizierten Knotenmenge gehen soll. c) Wie a), wobei der Pfad durch mindestens einen Knoten in jeder vonK spezifizierten Knotenmenge gehen soll.

     

Dynamic shortest path problems with time-varying costs

This paper concerns the problem of finding shortest paths from one node to all other nodes in networks for which arc costs can vary with time, each arc has a transit time, and parking with a corresponding time-varying cost is allowed at the nodes. The transit times can also take negative values. A general labeling method, as well as several implementations, are presented for finding shortest paths and detecting negative cycles under the assumption that arc traversal costs are piecewise linear and node parking costs are piecewise constant.     

Shortest path algorithms for knapsack type problems

The group knapsack and knapsack problems are generalised to shortest path problems in a class of graphs called knapsack graphs. An efficient algorithm is described for finding shortest paths provided that arc lengths are non-negative. A more efficient algorithm is described for the acyclic case which includes the knapsack problem. In this latter case the algorithm reduces to a known algorithm.     

Solvingk-shortest and constrained shortest path problems efficiently

In this paper, we examine the problems of finding thek-shortest paths, thek-shortest paths without repeated nodes, and the shortest path with a single side constraint between an origin and destination pair. Distances are assumed to be non-negative, but networks may be either directed or undirected. Two versions of algorithms for all these problems are compared. The computational results show that, in each case, the advantage of the adaptive version (as measured by total number of permanent labels) grows with the problem size.The views and opinions in this paper are strictly those of the authors and not necessarily those of the IBM Corporation.     

Error bounds for stochastic shortest path problems

For stochastic shortest path problems, error bounds for value iteration due to Bertsekas elegantly generalize the classic MacQueen–Porteus error bounds for discounted infinite-horizon Markov decision problems, but incur prohibitive computational overhead. We derive bounds on these error bounds that can be computed with little or no overhead, making them useful in practice—especially so, since easily-computed error bounds have not previously been available for this class of problems.     

Algorithms for time-dependent bicriteria shortest path problems

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.     

The generalized alternating path algorithm for transportation problems

A new primal extreme point algorithm for solving capacitated transportation problems is developed in this paper. This algorithm, called the generalized alternating path (GAP) algorithm, is a special purpose method specifically designed to take advantage of the often pervasive primal degeneracy of transportation problems.     

On a special class of bicriterion path problems

In this paper we are concerned with a special class of bicriterion path problems. For the considered class of bicriterion problems at least one of the objectives is type MAXMIN. For the other one, besides an objective type MAXMIN also a MINSUM and a MINRATIO type objective are considered. Two algorithms are presented for the considered class of bicriterion path problems. The first one only determines the minimal complete set of nondominated paths and the second one determines the entire set of nondominated paths. Both algorithms can be used for any type of bicriterion path problems, since one of the objectives is type MAXMIN and an algorithm exists to determine the best path for the other objective. Computational statistics for the three types of considered bicriterion path problems are also presented.     

An efficient algorithm for perturbed shortest path problems

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a minmax version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Partial difference equation method for lattice path problems

Many problems concerning lattice paths, especially on the square lattice have been exactly solved. For a single path, many methods exist that allow exact calculation regardless of whether the path inhabits a strip, a semi-infinite space or infinite space, or perhaps interacts with the walls. It has been shown that a transfer matrix method using the Bethe Ansatz allows for the calculation of the partition function for many non-intersecting paths interacting with a wall. This problem can also be considered using the Gessel-Viennot methodology. In a concurrent development, two non-intersecting paths interacting with a wall have been examined in semi-infinite space using a set of partial difference equations.Here, we review thispartial difference equation method for the case of one path in a half plane. We then demonstrate that the answer for arbitrary numbers of non-intersecting paths interacting with a wall can be obtained using this method. One reason for doing this is its pedagogical value in showing its ease of use compared to the transfer matrix method. The solution is expressed in a new form as a constant term formula, which is readily evaluated. More importantly, it is the natural method that generalizes easily to many intersecting paths where there is inter-path interactions (e.g., osculating lattice paths). We discuss the relationship of the partial difference equation method to the transfer matrix method and their solution via a Bethe Ansatz.     

Efficient reduction for path problems on circular-arc graphs

An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives anO(n+m) algorithm for proper circular-arc graphs, and anO(n+m) algorithm for general circular-arc graphs. This reduction also gives anO(n+m) algorithm for the two path problem on circular-arc graphs.     

Multiobjective shortest path problems with lexicographic goal-based preferences

Multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new exact label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive.     

Improved algorithms for path partition and related problems

We study the L_∞ path partition problem: given a path of n weighted vertices and an integer k, remove k−1 edges from the path so that the maximum absolute deviation of the weights of the resulting k sub-paths from their mean is minimized. Previously, the best algorithm solves this problem in O(nklogk) time. We present an O(nk) time algorithm. We also give improved solutions for two related problems: the L_d path partition problem and the web proxies placement problem.