Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

A locally optimal fast obstacle-avoiding path-planning algorithm

Two algorithms to compute the shortest collision-free paths in the Euclidean plane are presented. The ƒ obstacles assumed to be described by disjoint convex polygons having N vertices in total. After preprocessing time O(N+flogN), a suboptimal shortest path between two arbitrary query points can be found in O(f+NlogN) time using Dijkstra's algorithm and in Θ(N) time using the A¹ algorithm. The space complexity is O(N+f).     

A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem

The purpose of this study is to describe a data parallel primal-dual augmenting path algorithm for the dense linear many-to-one assignment problem also known as semi-assignment. This problem could for instance be described as assigning n persons to m(n) job groups.The algorithm is tailored specifically for massive SIMD parallelism and employs, in this context, a new efficient breadth-first-search augmenting path technique which is found to be faster than the shortest augmenting path search normally used in sequential algorithms for this problem. We show that the best known sequential computational complexity of O(mn ² ) for dense problems, is reduced to the parallel complexity of O(mn), on a machine with n processors supporting reductions in O(1) time. The algorithm is easy to implement efficiently on commercially available massively parallel computers. A range of numerical experiments are performed on a Connection Machine CM200 and a MasPar MP-2. The tests show the good performance of the proposed algorithm.     

Reconstructing shortest paths

This paper develops a polynomial-time algorithm that reconstructs a shortest path between two vertices using only the all pairs shortest path distance matrix. For graphs with positive edge weights, the algorithm requiresO(⦹V|log|V|) time. When the graph contains both positive and negative, but not zero, edge weights, and all cycles have positive length, the algorithm runs inO(|V|²) time. The remarkable feature about the algorithm is that it does not require explicit information about edges in the original graph.     

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.     

On the analysis of optimization problems in arc-dependent networks

This paper is concerned with the design and analysis of algorithms for optimization problems in arc-dependent networks. A network is said to be arc-dependent if the cost of an arc $a$ depends upon the arc taken to enter $a$. These networks are fundamentally different from traditional networks in which the cost associated with an arc is a fixed constant and part of the input. We first study the arc-dependent shortest path (ADSP) problem, which is also known as the suffix-1 path-dependent shortest path problem in the literature. This problem has a polynomial time solution if the shortest paths are not required to be simple. The ADSP problem finds applications in a number of domains, including highway engineering, turn penalties and prohibitions, and fare rebates. In this paper, we are interested in the ADSP problem when restricted to simple paths. We call this restricted version the simple arc-dependent shortest path (SADSP) problem. We show that the SADSP problem is NP-complete. We present inapproximability results and an exact exponential algorithm for this problem. We also extend our results for the longest path problem in arc-dependent networks. Additionally, we explore the problem of detecting negative cycles in arc-dependent networks and discuss its computational complexity. Our results include variants of the negative cycle detection problem such as longest, shortest, heaviest, and lightest negative simple cycles.²     

A new algorithm for the quasi-assignment problem

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n ³).The research for this paper was partly supported by the Chinese National Science Foundation.     

Dynamic programming algorithms for picture comparison

Two-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N⁶) for comparison of two N × N arrays. The computational complexity is reduced to O(N⁴) in general and O(N²) algorithms are pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains open.     

An O(n2) shortest path algorithm for a non-rotating convex body

We investigate the problem of moving a convex body in the plane from one location to another while avoiding a given collection of polygonal obstacles. The method we propose is applicable when the convex body is not allowed to rotate. If n denotes the total size of all polygonal obstacles, the method yields an O(n²) algorithm for finding a shortest path from the initial to the final location. In solving this problem, we develop some new tools in computational geometry that may be of independent interest.     

Using Random Quasi-Monte-Carlo Within Particle Filters,With Application to Financial Time Series

This article presents a new particle filter algorithm which uses random quasi-Monte-Carlo to propagate particles. The filter can be used generally, but here it is shown that for one-dimensional state-space models, if the number of particles is N, then the rate of convergence of this algorithm is N^?1. This compares favorably with the N^?1/2 convergence rate of standard particle filters. The computational complexity of the new filter is quadratic in the number of particles, as opposed to the linear computational complexity of standard methods. I demonstrate the new filter on two important financial time series models, an ARCH model and a stochastic volatility model. Simulation studies show that for fixed CPU time, the new filter can be orders of magnitude more accurate than existing particle filters. The new filter is particularly efficient at estimating smooth functions of the states, where empirical rates of convergence are N^?3/2; and for performing smoothing, where both the new and existing filters have the same computational complexity.     

An efficient numerical method for a mathematical model of a transport of coagulating particles

A new computational algorithm based on a fast way of computing integral operators describing the coagulation process is proposed for a mathematical model of coagulating particles. Using this algorithm, the computational complexity of each timestep of an explicit difference scheme can be substantially reduced. For each step, the complexity of execution is reduced from O(NM²) arithmetic operations to O(NMRlnM), where N is the number of mesh points along the physical coordinates of particles, M is the number of mesh points in a grid corresponding to sizes of coagulating particles, and R is the rank of a matrix corresponding to the values of the function of a coagulation kernel at mesh points. Using this approach, computations can be greatly accelerated, provided that kernel rank R is small.     

On the fast solution of a linear system arising in numerical conformal mapping

One step of the Newton method for the discretized Theodorsen equation in conformal mapping requires the solution of a certain 2N×2N system. Application of the Gaussian algorithm costs O(N³) arithmetic operations (a.o.). We present an algorithm which reduces the problem to the solution of three N×N linear Toeplitz systems. These systems can be solved in O(N log²N) a.o. This is also the amount of work required by the whole algorithm.     

Fast skew-feedback shift-register synthesis

A skew-feedback shift-register is a generalization of a linear-feedback shift-register and can be applied in decoding (interleaved) Reed–Solomon codes or Gabidulin codes beyond half their code distance. A fast algorithm is proposed which synthesizes all shortest skew-feedback shift-registers generating L sequences of varying length over a field. For fixed L, the time complexity of the algorithm is ${{\mathcal O}(M(N) \log N)}$ operations, where N is the length of a longest sequence and M(N) is the complexity of the multiplication of two skew polynomials of maximum degree N.     

The tricriterion shortest path problem with at least two bottleneck objective functions

The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let p(n) be the complexity of a classical single objective algorithm responsible for this third function, where n is the number of nodes and m be the number of arcs of the graph. An O(m²p(n)) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.     

A primal-dual interior point method whose running time depends only on the constraint matrix

We propose a primal-dual “layered-step” interior point (LIP) algorithm for linear programming with data given by real numbers. This algorithm follows the central path, either with short steps or with a new type of step called a “layered least squares” (LLS) step. The algorithm returns an exact optimum after a finite number of steps—in particular, after O(n ^3.5 c(A)) iterations, wherec(A) is a function of the coefficient matrix. The LLS steps can be thought of as accelerating a classical path-following interior point method. One consequence of the new method is a new characterization of the central path: we show that it composed of at mostn ² alternating straight and curved segments. If the LIP algorithm is applied to integer data, we get as another corollary a new proof of a well-known theorem by Tardos that linear programming can be solved in strongly polynomial time provided thatA contains small-integer entries.     

The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm

The multiperiod assignment problem, a specialization of the three dimensional assignment problem, is an optimization model that describes the situation of assigning people to activities, or jobs over time. We consider the most general case which has both a cost of assigning a person to an activity in each time period, and a cost of transferring the person from one activity in each period to another activity in the next period. In general, the number of time periods need not equal the number of persons and activities. We present a new formulation of the multiperiod assignment problem, that of an integer, multicommodity network flow model. The special structure of the model allows us to find a good feasible solution relatively quickly by a shortest path heuristic algorithm. We discuss a new branch and bound algorithm for solving this problem to optimality. The subproblems of the branch and bound tree are evaluated by solving a set of special-structured, shortest path problems all of which can be solved in order n²T time, where n is the number of persons and activities, and T is the number of time periods. We present computational tests of the algorithm on moderately sized problems.     

Asymptotically fast solution of toeplitz and related systems of linear equations

We present an inversion algorithm for the solution of a generic N X N Toeplitz system of linear equations with computational complexity O(Nlog²N) and storage requirements O(N). The algorithm relies upon the known structure of Toeplitz matrices and their inverses and achieves speed through a doubling method. All the results are derived and stated in terms of the recent concept of displacement rank, and this is used to extend the scope of the algorithm to include a wider class of matrices than just Toeplitz and also to include block Toeplitz matrices.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.