A new algorithm for reoptimizing shortest paths when the arc costs change

We propose the first algorithmic approach which reoptimizes the shortest paths when any subset of arcs of the input graph is affected by a change of the costs, which can be either lower or higher than the old ones. This situation is more general than the ones addressed in the literature so far. We analyze the worst-case time complexity of the algorithm as a function of both the input size and the overall cost perturbation, and discuss cases for which the proposed reoptimization method theoretically outperforms the approach of applying a standard shortest path algorithm after the change of the arc costs.     

Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

In this paper the problem of optimally guillotine cutting a rectangle (A, B  ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,_ai),i∈I$(c\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in J$ have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

Minimum cost flow algorithms for series-parallel networks

It is shown that an acyclic multigraph with a single source and a single sink is series-parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minumum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two O(mn+logm)-algorithms. One of them is based on the greedy scheme.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

Shortest paths algorithms: Theory and experimental evaluation

We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove interesting theoretical results suggested by the experimental data. Our computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in our research. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the NSF and Powell Foundation grants mentioned below. Andrew V. Goldberg was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation. Corresponding author. This work was done while Tomasz Radzik was a Postdoctoral Fellow at SORIE, Cornell University, and supported by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550, and by the Packard Fellowship of éva Tardos.     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

Parallel asynchronous label-correcting methods for shortest paths

We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI.     

An introduction to dynamic generative networks: Minimum cost flow

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.     

The robust shortest path problem in series-parallel multidigraphs with interval data

In this paper the robust shortest path problem in edge series-parallel multidigraphs with interval costs is examined. The maximal regret criterion is applied to calculate the optimal solution. It is shown that this problem is NP-hard. A pseudopolynomial algorithm for the studied problem is constructed.     

Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

Efficient Parallel Algorithms for the Minimum Cost Flow Problem

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the -relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the -relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.     

The robust shortest path problem with interval data via Benders decomposition

Many real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. In this paper we discuss the application of a Benders decomposition approach to this problem. Computational results confirm the efficiency of the new algorithm. It is able to clearly outperform state-of-the-art algorithms on many classes of networks. For the remaining classes we identify the most promising algorithm among the others, depending of the characteristics of the networks. Received: September 2004 / Accepted: March 2005 AMS classification: 90C47, 52B05, 90C57 The work was partially supported by the European Commission IST projects MOSCA (IST-2000-29557) and BISON (IST-2001-38923). All correspondence to: Roberto Montemanni     

Maximum network flows with concave gains

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. Supported by a Grant-in-Aid for Scientific Research (No. 13780351 and No.14380188) from The Ministry of Education, Culture, Sports, Science and Technology of Japan.