Abstract We present an algebraic approach for computing the distribution of the length of a shortests‐tpath, as well as the distribution of the capacity of a minimums‐tcut, in a network where the arc values (lengths and capacities) have known (discrete) probability distributions. For each problem, both exact and approximating algorithms are presented. These approximating algorithms are shown to yield upper and lower bounds on the distribution of interest. This approach likewise provides exact and bounding distributions on the maximum flow value in stochastic networks. We also obtain bounds on the expected shortest path length as well as the expected minimum cut capacity (and the expected maximum flow value). © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

We are proud to announce the winners of the Glover-

The classic Bellman-Ford algorithm for calculating shortest paths can be easily adapted to a distributed environment in which the computations are performed locally by identical processors at each network node. A distributed shortest-path algorithm is particularly appropriate for use in communication networks to capitalize on local information rather than rely on a central controller. This paper discusses the behavior of a synchronous version of the distributed Bellman-Ford algorithm in a dynamic environment in which communication link costs can undergo change. Several algorithms are described that mitigate or eliminate the occurrence of looping, which is responsible for degrading the performance of distributed shortest-path algorithms. We provide theoretical and computational evidence to show that two proposed algorithms offer improvements upon the original and modified Bellman-Ford algorithms.

An important task in the management and administration of communication networks is constructing routes for messages to follow from source to destination. A common approach is to route along the shortest available path connecting the source to the destination, where link lengths can be defined in a variety of ways (e.g., time, cost, impact on average queueing delay, or capacity required). This paper presents a family of novel minimax models for determining a set of paths from the source to the destination that are reasonably short in length while also reasonably diverse (disjoint). The overall goal is to design a routing scheme that is both ef.cient and robust, resulting in greater network reliability. Several models are investigated and a column-generation approach is proposed for exact solution. Computational results show that this exact technique can be applied effectively to moderate sized networks. For even larger networks, heuristic methods are developed and tested.

A problem encountered in the analysis of communication and other distribution systems is evaluating the performance of the system in meeting user demands with available resources. We consider the case in which user demands and available resources are only known stochastically and connecting links can operate at various levels. This situation can be modeled as a two-terminal stochastic network flow problem, in which each edge of the network assumes a finite number of values (corresponding to different capacity levels) with known probabilities. For each state of the network, we are interested in the maximum demand that can be met using the best allocation of resources. The approach used here to estimate the average unmet demand involves generating only “high leverage” states of the system—states having high probability and/or high values of unmet demand. A new algorithm is proposed for generating such states in monotone order, either by probability or by unmet demand. Bounds on the performance of the network are investigated.

This is a commentary to the McGeoch's feature article. The objective is to reinforce certain issues and to suggest conceptual framework for future exploration.

Abstract This paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.

The empirical performance of state enumeration methods proposed by several authors are examined, and refinements which result in significant computational improvements are presented. Two methods for state enumeration which compare favorably with the most efficient of current methods are introduced. They are based respectively on the work of S.-N. Chiou and V.O.K. Li (1986) and R.F. Gaebler and R.J. Chen (1987). It is shown that every algorithm discussed except that of C.L. Yang and P. Kubar (1989) can be executed significantly faster when the state enumeration problem is somewhat relaxed.>

The two-terminal reliability problem for an undirected network involves calculating the probability that two distinguished sites are connected by a path of working edges. This problem is known to be NP-hard, even for the special case of planar systems. We present efficient data structures and algorithms for manipulating planar networks and for generating both paths an cutsets in such networks. A pseudopolynomial algorithm is then implemented, based on these generation procedures, to calculate two-terminal reliability for planar networks; that is, the algorithm's time complexity is polynomially bounded in the number of paths (or the number of cutsets). Computational experience with this implementation is also presented, showing that it provides a substantial improvement over previous implementations of the pseudopolynomial algorithm. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

An algorithm is proposed for generating in order the most likely states of a probabilistic system, thus allowing a more-rapid procedure than previously available for analyzing the performance of communication networks with stochastically failing components. The algorithm improves the algorithm reported by Y. F. Lam and V.O.K. Li (ibid., vol.COM-34, no.5, p.496-7, May 1986), in terms of both storage requirements and execution efficiency.>

Abstract Several approaches for evaluating network reliability require the generation of all minimal cutsets in a directed graph. A general iterative algorithm, based on an underlying algebraic structure, is proposed for generating all minimal s−j cutsets simultancously for all vertices j in such a graph. In order to implement this algorithm in an efficient manner and to exploit sparsity present in the graph, a number of computational simplifications are developed, leading to improved performance of the algorithm. Empirical results show that the choice of certain data structures can have a profound effect on the computational effort required.

The problem of determining a minimum spanning tree arises in a number of application areas, including network reliability, pattern recognition, clustering, and design of distribution systems.The present algorithm implements Prim's procedure [7] for calculating a minimum spanning tree in an undirected network when the edge costs can be scaled to integers in a moderate range.While other codes for implementing Prim's procedure have been published [4,6,8, 9], all have used a two-dimensional array for storing the edge costs.As a result, such implementations have been limited to fairly small networks (e.g., 100 or fewer vertices).Moreover, these previous codes do not take advantage of network sparsity to reduce the computational effort.In contrast, the present code does exploit network sparsity and has been used to calculate minimum spanning trees for networks with up to 500 vertices and 24,000 edges.Even such large problems required less than 0.7 seconds of CPU time on an IBM 370/3033 computer (IBM Extended H FORTRAN compiler).For the algorithm given here, the edge costs are assumed to be positive integers with maximum edge cost CMAX.The network, assumed to be connected with NV vertices, is represented in forward star form [2,3].That is, for each vertex i E {1 ..... NV}, EPT(i) is a pointer to the first position in a list ELIST where the vertices j adjacent to i are stored consecutively.A list ECOST, of the same size as ELIST, stores the corresponding edge costs c(i, j) for the edges (i, j).It

Abstract This paper studies one aspect of the “robustness” of optimal solutions to shortest path and, more generally, network flow problems. Specifically, we characterize the maximum increase and the maximum decrease in an arc's cost that can be tolerated without changing optimality of the current solution. Calculation of these quantities is quite simple for nonbasic arcs, and somewhat more involved for basic arcs. When such tolerances are to be determined simultaneously for all arcs in the network, considerable duplication of effort can be avoided through the use of specialized algorithms. Several algorithms for calculating all arc tolerances are presented, one of which is shown to have complexity order n2 for general networks with n nodes.

Described here are the theoretmal development and computer implementation of a procedure that generates test problems for L~ esth-nation of the linear model y= Xfl + u.The generation procedure allows the user flembdlty m specifying the problem dimensions, the LI solution vector fl*, the distribution of the observed residuals ~, as well as the column rank, row repetitions, and degree of degeneracy of the matrix X The user can also specify the distributional form, mean, and variance for each independent variable An lraportant feature of the generator is that any problem it creates is guaranteed to have a umque solutmn ~ whenever X has full rank Key Words and Phrases.L1 approximation, least absolute dewation, problem generator, test data CR Categories: 5.13, 5.41, 5.5

article Free AccessArtifacts AvailableArtifacts Evaluated & Reusable Share on Algorithm 564: A Test Problem Generator for Discrete Linear L1 Approximation Problem Authors: K. L. Hoffman Center for Applied Mathematics, National Bureau of Standards, Washington, DC Center for Applied Mathematics, National Bureau of Standards, Washington, DCView Profile , D. R. Shier Center for Applied Mathematics, National Bureau of Standards, Washington, DC Center for Applied Mathematics, National Bureau of Standards, Washington, DCView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 6Issue 4Dec. 1980 pp 615–617https://doi.org/10.1145/355921.355932Published:01 December 1980Publication History 1citation255DownloadsMetricsTotal Citations1Total Downloads255Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract This paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated.

Abstract This paper presents and develops an algebraic structure for determining the k shortest paths from a given node to all other nodes of a network. Three new methods for calculating such k shortest path information are examined and compared. These methods are based on a fairly strong analogy which exists between the solution of such network problems and traditional techniques for solving linear equations. On the basis of both theoretical and computational evidence, one of the three methods is seen to offer an extremely effective procedure for finding the k shortest paths from a given node in a network.