A Zero-Space algorithm for Negative Cost Cycle Detection in networks

This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. The Negative Cost Cycle Detection (NCCD) problem is one of the more fundamental problems in network design and finds applications in a number of domains ranging from Network Optimization and Operations Research to Constraint Programming and System Verification. As per the literature, approaches to this problem have been either Relaxation-based or Contraction-based. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the NCCD problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is as efficient as the fastest known comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes O(mn) time to detect the presence of a negative cost cycle or to report that none exists. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require Ω(n) extra space. It is well known that the NCCD problem is closely related to the Single Source Shortest Paths (SSSP) problem, i.e., the problem of determining the shortest path distances of all the vertices in a network, from a specified source; indeed most algorithms in the literature for the NCCD problem are modifications of approaches to the SSSP problem. At this juncture, it is not clear whether the Stressing Algorithm could be extended to solve the SSSP problem, even if O(n) extra space is available.     

A note onK best network flows

It is shown that the problem of finding theK best solutions of a linear integer network flow problem can be solved by a polynomial time algorithm. This algorithm can be used in order to solve a multiple-criteria network flow problem which minimizes the maximum ofQ objectives.Partially supported by grants of the Deutsche Forschungsgemeinschaft and the HC&M programme of the European Union under ERBCHRXCT 930087.     

An O(T log T) Algorithm for the Dynamic Lot Size Problem with Limited Storage and Linear Costs

In this paper the dynamic lot size problem with time varying storage capacities and linear costs is addressed. Like in the uncapacitated version, this problem can be formulated as a network flow problem. Considering the properties of the underlying network, we devise an O(T log T) greedy algorithm to obtain optimal policies and we report computational results for randomly generated problems.     

The multi-weighted Steiner tree problem

We formulate and investigate the Multi-Weighted Steiner Problem (MWS), a generalization of the Steiner problem in graphs, involving more than one weight function. As a special case, it contains the hierarchical network design problem. With the notion of "bottleneck length/distance", a min-max measure, we analyze the interaction between differently weighted edges in a solution. Combining the results with known methods for the Steiner problem in graphs and the hierarchical network design problem, two heuristics for the MWS are developed, one based on weight modifications and the other on exchanging edges. Both are of time complexityO(kv ²), withv the number of nodes andk the number of special nodes in the graph. The first is also suited for thedirected MWS; the second is expected to perform better on the undirected version. Before actually solving the Steiner problem in graphs and the hierarchical network design problem, preprocessing techniques exploiting tests to reduce the problem graphs have proven to be valuable. We adapt three prominent tests for use in the MWS.     

An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v≠s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v≠s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

A method for maximizing the reliability coefficient of a communications network

The most common idea of network reliability in the literature is a numerical parameter calledoverall network reliability, which is the probability that the network will be in a successful state in which all nodes can mutually communicate. Most papers concentrate on the problem of calculating the overall network reliability which is known to be an NP hard problem. In the present paper, the question asked is how to find a method for determining a reliable subnetwork of a given network. Givenn terminals and one central computer, the problem is to construct a network that links each terminal to the central computer, subject to the following conditions: (1) each link must be economically feasible; (2) the minimum number of links should be used; and (3) the reliability coefficient should be maximized. We argue that the network satisfying condition (2) is a spanning arborescence of the network defined by condition (1). We define the idea of thereliability coefficient of a spanning arborescence of a network, which is the probability that a node at average distance from the root of the arborescence can communicate with the root. We show how this coefficient can be calculated exactly when there are no degree constraints on nodes of the spanning arborescence, or approximately when such degree constraints are present. Computational experience for networks consisting of up to 900 terminals is given.This report was prepared as part of the activities of the Management Science Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047–048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

On connected domination in unit ball graphs

Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.     

A new strongly polynomial dual network simplex algorithm

This paper presents a new dual network simplex algorithm for the minimum cost network flow problem. The algorithm works directly on the original capacitated network and runs in O(mn(m +n logn) logn) time for the network withn nodes andm arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos’ (1993) dual network simplex algorithm by a factor ofm/n.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A polynomial-time simplex method for the maximumk-flow problem

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c _e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc _e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

On duality and fractionality of multicommodity flows in directed networks

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span T_μ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on T_μ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min–max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov–Frank theorem for directed free multiflows and Ibaraki–Karzanov–Nagamochi’s directed multiflow locking theorem as special cases.     

The minimum shift design problem

The min-Shift Design problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. Our research considers both theoretical and practical aspects of the min-Shift Design problem. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic hardness of approximation lower bound for MSD. On the basis of these results, we propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a local search algorithm. The greedy part is based on the network flow analogy, and the local search algorithm makes use of multiple neighborhood relations. An experimental analysis on structured random instances shows that the hybrid heuristic clearly outperforms our previous commercial implementation. Furthermore, it highlights the respective merits of the composing heuristics for different performance parameters.     

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.     

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths. A natural approach to this problem is through a multicommodity flow reduction. However, we show that the random walk approach leads to significantly stronger‐results than those recently obtained by Leighton and Rao [Proc. of 9th International Parallel Processing Symposium, 1995] using the multicommodity flow setup. In the dynamic version of the problem connection requests are continuously injected into the network. Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the path is deleted. Again each edge in the network should not be used by more than g paths at once. The dynamic version is a better model for the practical use of communication networks. Our random walk approach gives a simple and fully distributed solution for this problem. We show that if the injection to the network and the duration of connection are both controlled by Poisson processes then our algorithm achieves a steady state utilization of the network which is similar to the utilization achieved in the static case situation. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 87–109, 1999