On the second point-to-point undirected shortest simple path problem

We address the determination of the second point-to-point shortest simple path in undirected networks. The effective reduced cost concept is introduced to compute the second best solution. This concept is used to prove that a path tree containing the second point-to-point shortest simple path is adjacent to any shortest path tree. Therefore, this result immediately implies a method requiring O(m) time once that the shortest path tree is obtained on an undirected network with n nodes and m edges.     

The weight of the shortest path tree

The minimal weight of the shortest path tree in a complete graph with independent and exponential (mean 1) random link weights is shown to converge to a Gaussian distribution. We prove a conditional central limit theorem and show that the condition holds with probability converging to 1. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A spreadsheet modelling approach to the assortment problem

A list of similar items of different sizes are required on a regular basis, but it is impractical to stock each of the different sizes. Demands for any size that is not stocked must be met by supplying the nearest acceptable size that is stocked, resulting in increased cost or trim wastage for example. The problem of determining which sizes should be stocked to minimise or maximise an appropriate objective function is formulated as a shortest or longest path problem on a directed acyclic network. A spreadsheet model is used to solve the problem, in such a way that showing precedents on the spreadsheet results in the basis tree for the shortest or longest path solution being drawn without the need for special software. The basis tree produced by this method is shown to be planar for practical applications, enabling improved efficiency of the algorithm used. Examples are given to illustrate the application of this approach.     

A distributed algorithm for equitable bandwidth allocation for content distribution in a tree network

We present a distributed algorithm for bandwidth allocation for content distribution in tree networks, where the intensive computations are executed independently at the nodes while some information is exchanged among the nodes. The root node has a server that stores and broadcasts multiple programs requested at the nodes through links with limited capacity. The bandwidth allocated for a specific program can be decreased from one link to the next in a path from the root node to an end-node, but it cannot be increased. The objective is to determine equitable bandwidth allocations among all programs across all links, which leads to a formulation of a lexicographic maximin optimization model. The performance function at each of the nodes for a specific program represents customers’ satisfaction as a function of the incoming bandwidth into the node. The distributed algorithm that determines the equitable bandwidth allocations extends the algorithm described in Luss (2010).     

Reliability function of a class of time-dependent systems with standby redundancy

By applying shortest path analysis in stochastic networks, we introduce a new approach to obtain the reliability function of time-dependent systems with standby redundancy. We assume that not all elements of the system are set to function from the beginning. Upon the failure of each element of the active path in the reliability graph, the system switches to the next path. Then, the corresponding elements are activated and consequently the connection between the input and the output is established. It is also assumed each element exhibits a constant hazard rate and its lifetime is a random variable with exponential distribution. To evaluate the system reliability, we construct a directed stochastic network called E-network, in which each path corresponds with a minimal cut of the reliability graph. We also prove that the system failure function is equal to the density function of the shortest path of E-network. The shortest path distribution of this new constructed network is determined analytically using continuous-time Markov processes.     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

Characterization of the Distance between Subtrees of a Tree by the Associated Tight Span

A characterization is given to the distance between subtrees of a tree defined as the shortest path length between subtrees. This is a generalization of the four-point condition for tree metrics. For this, we use the theory of the tight span and obtain an extension of the famous result by Dress that a metric is a tree metric if and only if its tight span is a tree. Received July 13, 2004     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

Approximation of min–max and min–max regret versions of some combinatorial optimization problems

This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.     

Asymptotics for a censored generalized linear model with unknown link function

For censored response variable against projected co-variable, a generalized linear model with an unknown link function can cover almost all existing models under censorship. Its special cases include the accelerated failure time model with censored data. Such a model in the uncensored case is called the single-index model in econometrics. In this paper, we systematically study the asymptotic properties. We derive the central limit theorem and the law of the iterated logarithm for an estimator of the direction parameter. We also obtain the optimal convergence rate of an estimator of the unknown link function in the model.      

Asymptotic description of stochastic neural networks. I. Existence of a large deviation principle

We study the asymptotic law of a network of interacting neurons when the number of neurons becomes infinite. The dynamics of the neurons is described by a set of stochastic differential equations in discrete time. The neurons interact through the synaptic weights that are Gaussian correlated random variables. We describe the asymptotic law of the network when the number of neurons goes to infinity. Unlike previous works which made the biologically unrealistic assumption that the weights were i.i.d. random variables, we assume that they are correlated. We introduce the process-level empirical measure of the trajectories of the solutions into the equations of the finite network of neurons and the averaged law (with respect to the synaptic weights) of the trajectories of the solutions into the equations of the network of neurons. The result ( Theorem 3.1 below) is that the image law through the empirical measure satisfies a large deviation principle with a good rate function. We provide an analytical expression of this rate function in terms of the spectral representation of certain Gaussian processes.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

Branch-and-price algorithm for a multicast routing problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.     

Sharp estimates and a central limit theorem for the invariant law for a large star-shaped loss network

Calls arrive in a Poisson stream on a symmetric network constituted of N links of capacity C. Each call requires one channel on each of L distinct links chosen uniformly at random; if none of these links is full, the call is accepted and holds one channel per link for an exponential duration, else it is lost. The invariant law for the route occupation process has a semi-explicit expression similar to that for a Gibbs measure: it involves a combinatorial normalizing factor, the partition function, which is very difficult to evaluate. We study the large N limit while keeping the arrival rate per link fixed. We use the Laplace asymptotic method. We obtain the sharp asymptotics of the partition function, then the central limit theorem for the empirical measure of the occupancies of the links under the invariant law. We also obtain a sharp version for the large deviation principle proved in Graham and O'Connell (Ann. Appl. Probab. 10 (2000) 104).     

Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding

We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space using the concept of funnels associated with common edges along the sequence of triangles and the planar unfolding for each funnel. We show that the unfolded image of a funnel is a simple polygon, it thus is non-overlapping. Therefore, such funnels are determined iteratively to their associated common edges by the planar unfolding and the shortest path joining two points is determined by cusps of these funnels.     

On a negative-equivalency theorem in associative optimal path problems

In this we study a wide class of optimal path problem in acyclic digraphs, where path lengths are defined through associative binary operations:addition, multiplication, multiplication-addition, fraction and so on. Solving a system of two interrelated recur-sive equations, we simultaneously find both shortest and longest path lengths, Further, for every problem (primal problem), we associate the other related problem (negative-equivalent problem) where each path length is defined through the associative operation connected to it in the primal problem by DeMorgan’s law. The main objective of this paper is to derive a negative-equivalency theorem between the primal problem and the negative-equivalent one     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

灾区巡视路线的分析

本问题是一个典型的最短回路问题 ,我们借助于最小生成树法和动态规划的方法 (用点权代替边权 ) ,建立了三个模型 ,再运用重绕最小生成树法求解三个模型 .在整个过程中我们还运用了 AUTOCAD制图、EXCEL制表、WORD和 WORDPRO处理文档 ,以及其他一些计算机软件 .本文的模型具有较强的实用性和普遍性 .建模过程中 ,用点权代替边权 ,是对动态规划的一个合理推广 .