We provide faster strongly polynomial time algorithms solving maximum flow in structured \(n\)-node \(m\)-arc networks. Our results imply an \(n^{\omega+o(1)}\)-time strongly polynomial time algorithms for computing a maximum bipartite \(b\)-matching where \(\omega\) is the matrix multiplication constant. Additionally, they imply an \(m^{1+o(1)}W\)-time algorithm for solving the problem on graphs with a given tree decomposition of width \(W\).

We present an O(nm) algorithm for all-pairs shortest paths computations in a directed graph with n nodes, m arcs, and nonnegative integer arc costs. This matches the complexity bound attained by Thorup [26] for the all-pairs problems in undirected graphs. Our main insight is that shortest paths problems with approximately balanced directed cost functions can be solved similarly to the undirected case. Our algorithm starts with an preprocessing step that finds a 3-min-balanced reduced cost function. Using these reduced costs, every shortest path query can be solved in O(m) time using an adaptation of Thorup's component hierarchy method. The balancing result is of independent interest, and gives the best currently known approximate balancing algorithm for the problem.

Abstract In 2013, Orlin proved that the max flow problem could be solved in O(nm) time. His algorithm ran in O(nm + m1.94) time, which was the fastest for graphs with fewer than n1.06 arcs. If the graph was not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan. We describe a new variant of the excess scaling algorithm for the max flow problem whose running time strictly dominates the running time of the algorithm by King et al. For graphs in which m = O(nlog n), the running time of our algorithm dominates that of King et al. by a factor of O(loglog n). Moreover, our algorithm achieves this improved performance without reliance on dynamic trees.

In this paper, we introduce an O(nm) time algorithm to determine the minimum length directed cycle (also called the "minimum weight directed cycle") in a directed network with n nodes and m arcs and with no negative length directed cycles.This result improves upon the previous best time bound of O(nm + n 2 log log n).Our algorithm first determines the cycle with minimum mean length λ * in O(nm) time.Subsequently, it chooses node potentials so that all reduced costs are λ * or greater.It then solves the all pairs shortest path problem, but restricts attention to paths of length at most nλ * .We speed up the shortest path calculations to O(m) per source node, leading to an O(nm) running time in total.We also carry out computational experiments comparing the performance of the proposed methods and other state-of-the-art methods.Experiments confirmed that it is advantageous to solve the minimum mean cycle problem prior to solving shortest path problems.Analysis of our experiments suggest that the running time to solve the minimum length directed cycle problem was much faster than O(n 2 ) on average. Introduction.We address the determination of the Minimum Length Directed Cycle (MLDC) in a graph G = (V, A) with n nodes and m arcs and with no negative length directed cycles.(Elsewhere, researchers have referred to the MLDC as the minimum weight directed cycle or the minimum cost directed cycle.)Floyd [12] and Warshall [32] showed how to solve this problem in O(n 3 ) time.An alternative approach is to find shortest paths between all pairs of nodes.In case there are negative length arcs, the first shortest path problem is solved using the label correcting algorithm.Subsequently, one can use reduced costs to transform the problem into an equivalent problem with nonnegative arc lengths.The subsequent n -1 shortest path problems are solved using Dijkstra's Algorithm.Using the shortest path algorithm of Fredman and Tarjan [14], the running time *

Infeasible network flow problems with supplies and demands can be characterized via violated cut‐inequalities of the classical Gale‐Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature by showing a one‐to‐one correspondence between IISs and Gale‐Hoffman‐inequalities in which one side of the cut has to be weakly connected. We also show that a single max‐flow computation allows one to compute an IIS. Moreover, we prove that finding an IIS of minimal cardinality in this special case of flow networks is strongly ‐hard. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 121–129 2016

We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely, the calculus of $K$-approximation functions and the calculus of $K$-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed.

In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m31/16 log2 n) time. In the case that m = O(n1.06), this improves upon the best previous algorithm due to King, Rao, and Tarjan, who solved the max flow problem in O(nm logm/(n log n)n) time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n2/ log n).

Abstract The pseudoflow algorithm for solving the maximum flow and minimum cut problems was devised in Hochbaum (2008). The complexity of the algorithm was shown in (2008) to be O(nm log n). Chandran and Hochbaum, (2009) demonstrated that the pseudoflow algorithm is very efficient in practice, and that the highest label version of the algorithm tends to perform best. Here, we improve the running time of the highest label pseudoflow algorithm to O(n3) using simple data structures and to O(nm log (n2/m)) using the dynamic trees data structure. Both these algorithms use a new form of Depth‐First‐Search implementation that is likely to be fast in practice as well. In addition, we give a new simpler description of the pseudoflow algorithm by relating it to the simplex algorithm as applied to the maximum preflow problem defined here. The interpretation of the generic pseudoflow algorithm as a simplex‐like algorithm for the maximum preflow problem motivates the pseudoflow algorithm and highlights differences between the pseudoflow algorithm and the preflow‐push algorithm of Goldberg and Tarjan. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract We develop efficient algorithms to solve convex cost flow problems where the underlying graph is a circle, a line, or a tree. Each node i has an associated supply/demand b( i). The cost of sending flow on arc ( i, j) is a piecewise linear convex function fij defined over . Let n be the number of nodes and m = O(n) be the total number of pieces of all the convex functions. A flow x is feasible if the imbalances on all nodes are nonnegative. Excess stored on node i has an associated linear cost . We show that the problem on a circle can be transformed into an equivalent problem on a line in O( n) time. Thereafter, we develop an algorithm that solves the problem on a line in time, where sort( n) is the time to sort n real numbers and is the inverse Ackermann function. We also prove that when the nodes lie on a tree, the problem can be solved in time using the dynamic tree data structure. We describe applications in areas such as distributed computing, lot‐sizing, computational biology, computational music, and transportation. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(4), 288–296 2013

Two-phase routing, where traffic is first distributed to intermediate nodes before being routed to the final destination, has been recently proposed for handling widely fluctuating traffic without the need to adapt network routing to changing traffic. Preconfiguring the network in a traffic-independent manner using two-phase routing simplifies network operation considerably. In this paper, we extend this routing scheme by providing resiliency against link failures through end-to-end shared backup path restoration. We view this as important progress toward adding carrier-class reliability to the robustness of the scheme so as to facilitate its future deployment in Internet service provider (ISP) networks. In shared backup path restoration, each connection consists of a link-disjoint primary and backup path pair; two backup paths can share bandwidth on their common links if their primary paths are link-disjoint. We show that the optimization problem for maximum throughput two-phase routing with shared backup path restoration is NP-hard. Assuming an approximation oracle for a certain disjoint paths problem (called SBPR-DISJOINT-PATHS, which is also NP-hard) involving the dual variables of a path indexed linear programming formulation for the problem, we design a combinatorial algorithm with provable guarantees. We also provide heuristics for finding approximating solutions to the SBPR-DISJOINT-PATHS problem. We evaluate the throughput performance and number of intermediate nodes in two-phase routing for the above and other restoration mechanisms for two-phase routing on actual ISP topologies collected for the Rocketfuel project and three research network topologies.

We give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher's market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We first develop a weakly polynomial time algorithm that runs in O(n4 log Umax + n3 emax) time, where n = |B| + |G|. We further modify the algorithm so that it runs in O(n4 log n) time. These algorithms improve upon the previous best running time of O(n8 log Umax + n7 log emax), due to Devanur et al.

This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n6EO log nM) time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O((n4EO + n5) log nM) time. The strongly polynomial version of this faster algorithm runs in O((n5EO + n6) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization. The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

Abstract We present a new efficient approach for solving the multicommodity flow problem as a sequence of subproblems, each on a very sparse but connected network. We show that each subproblem can be contracted to a problem on a much smaller graph. We then solve these problems using the simplex method. We test the algorithm on benchmark instances, and show its improvement over the usual simplex algorithm. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

We examine a selective list of combinatorial optimization problems in NP with respect to inapproximability (Arora and Lund (1997)) given that the ground set of elements N has additional characteristics. For each problem in this paper, the set N is expressed explicitly by subsets of N either as a partition or in the form of a cover. The problems examined are generalizations of well-known classical graph problems and include the minimal spanning tree problem, a number of elementary machine scheduling problems, the bin-packing problem, and the travelling salesman problem (TSP). We conclude that for all these generalized problems the existence of a polynomial time approximation scheme (PTAS) is impossible unless P=NP. This suggests a partial characterization for a family of inapproximable problems. For the generalized Euclidean TSP we prove inapproximability even if the subsets are of cardinality 2.

The fleet-assignment model (FAM) for an airline assigns fleet types to the set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. A through connection at a station is a connection between an arrival flight and a departure flight at the station, both of which have the same fleet type assigned to them, which ensures that the same plane flies both legs. Typically, passengers are willing to pay a premium for through connections. The through-assignment model (TAM) identifies a set of profitable throughs between arrival and departure flights flown by the same fleet type at each station to maximize the through benefits. TAM is usually solved after obtaining the solution from FAM. In this sequential approach, TAM cannot change the fleeting to get a better through assignment, and FAM does not take into account the through benefits. The goal of the combined through-fleet-assignment model (ctFAM) is to come up with a fleeting and through assignment that achieves the maximum combined benefit of the integrated model. We give a mixed integer-programming (MIP) formulation of ctFAM that is too large to be solved to even near optimality within allowable time for the data obtained by a major U.S. airline. We thus focus on neighborhood search algorithms for solving ctFAM, in which we start with the solution obtained by the previous sequential approach (that is, solving FAM first, followed by TAM) and improve it successively. Our approach is based on generalizing the swap-based neighborhood search approach of Talluri (1996) for FAM, which proceeds by swapping the fleet assignment of two flight paths flown by two different plane types that originate and terminate at the same stations and the same times. An important feature of our approach is that the size of our neighborhood is very large; hence the suggested algorithm is in the category of very large-scale neighborhood (VLSN) search algorithms. Another important feature of our approach is that we use integer programming to identify improved neighbors. We provide computational results that indicate that the neighborhood search approach for ctFAM provides substantial savings over the sequential approach of solving FAM and TAM.

The quadratic assignment problem (QAP) consists of assigning n facilities to n locations to minimize the total weighted cost of interactions between facilities. The QAP arises in many diverse settings, is known to be NP-hard, and can be solved to optimality only for fairly small instances (typically, n ≤ 30). Neighborhood search algorithms are the most popular heuristic algorithms for solving larger instances of the QAP. The most extensively applied neighborhood structure for the QAP is the 2-exchange neighborhood. This neighborhood is obtained by swapping the locations of two facilities; its size is therefore O(n2). Previous efforts to explore larger neighborhoods (such as 3-exchange or 4-exchange neighborhoods) were not very successful, as it took too long to evaluate the larger set of neighbors. In this paper, we propose very large-scale neighborhood (VLSN) search algorithms when the size of the neighborhood is very large, and we propose a novel search procedure to enumerate good neighbors heuristically. Our search procedure relies on the concept of an improvement graph that allows us to evaluate neighbors much faster than existing methods. In this paper, we present extensive computational results of our algorithms when applied to standard benchmark instances.

Abstract — We consider the realization of traffic-oblivious routing in IP-over-Optical networks where routers are interconnected over a switched optical backbone, also called IP-over-OTN (Optical Transport Network). The traffic-oblivious routing we consider is a scheme where incoming traffic is first distributed in a preset manner to a set of intermediate nodes. The traffic is then routed from the intermediate nodes to the final destination. This splitting of the routing into two-phases simplifies network configuration significantly [8], [17]. In implementing this scheme, the first and second phase paths are realized at the optical layer with router packet grooming at a single intermediate node only. Studies like [10] indicate that IP routers are 200 times more unreliable than traditional carrier-grade switches and average 1219 minutes of down time per year. Given this unreliability of routers, we consider how two-phase routing in IP-over-OTN can be made resilient against router node failures. We propose two different schemes for provisioning the optical layer to handle router node failures – one that is failure node independent and static, and the other that is failure node dependent and dynamic. We develop linear programming formulations for both schemes and a fast combinatorial algorithm for the second scheme so as to maximize network throughput. In each case, we determine (i) the optimal distribution of traffic to various intermediate routers for both normal (no-failure) and failure conditions, and (ii) provisioning of optical layer circuits to provide the needed inter-router links. We evaluate the performance of the two router failure protection schemes (in terms of throughput) and compare it with that of unprotected routing. For our experiments, we use actual ISP network topologies collected for the Rocketfuel project. I.

The emergence of new applications on the Internet like voice-over-IP, peer-to-peer, and video-on-demand has created highly dynamic and changing traffic patterns. In order to route such traffic with Quality-of-Service (QoS) guarantees without requiring detection of traffic changes in real-time or reconfiguring the network in response to it, we consider a routing and bandwidth allocation scheme that allows preconfiguration of the network such that all traffic patterns permissible within the network’s natural ingress-egress capacity constraints can be handled in a capacity efficient manner. The scheme routes traffic in two phases. In the first phase, incoming traffic is sent from the source to a set of intermediate nodes and then, in the second phase, from the intermediate nodes to the final destination. The traffic in the first phase is distributed to the intermediate nodes in predetermined proportions that depend on the intermediate nodes. In this paper, we develop linear programming formulations and a fast combinatorial algorithm for routing under the scheme so as to maximize throughput (or, minimize maximum link utilization). We compare the throughput performance of the scheme with that of the optimal scheme among the class of all schemes that are allowed to even make the routing dependent on the traffic matrix. For our evaluations, we use actual Internet Service Provider topologies collected for the Rocketfuel project. We also bring out the versatility of the scheme in not only handling widely fluctuating traffic but also accommodating applicability to several widely differing networking scenarios, including (i) economical Virtual Private Networks (VPNs), (ii) supporting indirection in specialized service overlay models like Internet Indirection Infrastructure (i3), (iii) adding QoS guarantees to services that require routing through a network-based middlebox, and (iv) reducing IP layer transit traffic and handling extreme traffic variability in IP-over-Optical networks without dynamic reconfiguration of the optical layer. The two desirable properties of supporting indirection in specialized service overlay models and static optical layer provisioning in IP-over-Optical networks are not present in other approaches for routing variable traffic, such as direct source-destination routing along fixed paths.

We consider the realization of traffic-oblivious rout- ing in IP-over-Optical networks where routers are interconnected over a switched optical backbone. The traffic-oblivious routing we consider is a scheme where incoming traffic is first distributed in a preset manner to a set of intermediate nodes. The traffic is then routed from the intermediate nodes to the final destination. This splitting of the routing into two phases simplifies network configuration significantly. In implementing this scheme, the first and second phase paths are realized at the optical layer with router packet grooming at a single intermediate node only. Stud- ies like (13) indicate that IP routers are 200 times more unreliable than traditional carrier-grade switches and average 1219 minutes of down time per year. Given this unreliability of routers, we consider how two-phase routing in IP-over-Optical networks can be made resilient against router node failures. We propose two different schemes for provisioning the optical layer to handle router node failures - one that is failure node independent and static, and the other that is failure node dependent and dynamic. We develop linear programming formulations for both schemes and a fast combinatorial algorithm for the second scheme so as to maximize network throughput. In each case, we determine (i) the optimal distribution of traffic to various intermediate routers for both normal (no-failure) and failure conditions, and (ii) provisioning of optical layer circuits to provide the needed inter-router links. We evaluate the performance of the two router failure protection schemes (in terms of throughput) and compare it with that of unprotected routing.

In this article we present a theoretical analysis of the online Sum-of-Squares algorithm ( SS ) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s ( a ) are integral (or can be scaled to be so), and runs in time O ( nB ). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O (log n ). We also discuss several interesting variants on SS , including a randomized O ( nB log B )-time online algorithm SS * whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS * depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F , just what is the growth rate for the optimal expected waste.

Abstract The fleet assignment model (FAM) for an airline assigns fleet types to a set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. The through assignment model matches inbound flight legs into a city with the outbound flight legs at the same city that are flown by the same plane types and creates through connections (that is, flight connections with one stopover). The combined through and fleet assignment model (ctFAM) integrates both the models into a single model and obtains optimal fleet and through assignments by varying both sets of decision variables simultaneously. In a recent article, Ahuja et al. ( 2001 ) proposed a very large‐scale neighborhood (VLSN) search algorithm for the ctFAM. In this article, we generalize this approach to incorporate time windows. In the model considered in this article, each flight leg has a time window associated with its departure time. The objective is to determine fleet assignment, departure time of all flight legs, and through connections between flights to minimize the total cost of fleet assignment and through connections. We call this model ctFAM with time windows or ctFAM‐TW. Allowing flexibility in the flight departure time creates greater opportunities for fleet assignment and through connections, and can reduce costs substantially. We describe the details of a VLSN search algorithm for ctFAM‐TW and also present computational results of our algorithm on the data provided by a large U.S. airline. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 160–171 2004

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of $\varepsilon$-local optimality and show that, for every $\varepsilon > 0$, an $\varepsilon$-local optimum can be identified in time polynomial in the problem size and $1/\varepsilon$ whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a $\delta$-local optimum, a variation of our main algorithm produces a $(\delta + \varepsilon)$-local optimum in time polynomial in the problem size and $1/\varepsilon$. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme.

Abstract In this paper, we study dynamic shortest path problems that determine a shortest path from a specified source node to every other node in the network where arc travel times change dynamically. We consider two problems: the minimum‐time walk problem and the minimum‐cost walk problem. The minimum‐time walk problem is to find a walk with the minimum travel time. The minimum‐cost walk problem is to find a walk with the minimum weighted sum of the travel time and the excess travel time (over the minimum possible travel time). The minimum‐time walk problem is known to be polynomially solvable for a class of networks called FIFO networks. In this paper, (i) we show that the minimum‐cost walk problem is an NP‐hard problem; (ii) we develop a pseudopolynomial‐time algorithm to solve the minimum‐cost walk problem (for integer travel times); and (iii) we develop a polynomial‐time algorithm for the minimum‐time walk problem arising in road networks with traffic lights. © 2003 Wiley Periodicals, Inc.

Abstract Let G = (N, A) be a network with a designated source node s, a designated sink node t, and a finite integral capacity uij on each arc (i, j) ∈ A. An elementary K‐flow is a flow of K units from s to t such that the flow on each arcis 0 or 1. A K‐route flow is a flow from s to t that may be expressed as a nonnegative linear sum of elementary K‐flows. In this paper, we show how to determine a maximum K‐route flow as a sequence of O(min {log (nU), K}( maximum‐flow problems. This improves upon the algorithm by Kishimoto, which solves this problem as a sequence of K maximum‐flow problems. In addition, we have simplified and extended some of the basic theory. We also discuss the application of our technique to Birkhoff's theorem and a scheduling problem. © 2001 John Wiley & Sons, Inc.

Abstract An inverse optimization problem is defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x0 ∈ S. We want to perturb the cost vector c to d so that x0 is an optimal solution of P with respect to the cost vector d, and w∥d − c∥p is minimum, where ∥ · ∥p denotes some selected lp norm and w is a vector of weights. In this paper, we consider inverse minimum‐cut and minimum‐cost flow problems under the l1 normal (where the objective is to minimize ∑j∈Jwj|dj − cj| for some index set J of variables) and under the l∞ norm (where the objective is to minimize max{wj|dj − cj|: j ∈ J}). We show that the unit weight (i.e., wj = 1 for all j ∈ J) inverse minimum‐cut problem under the l1 norm reduces to solving a maximum‐flow problem, and under the l∞ norm, it requires solving a polynomial sequence of minimum‐cut problems. The unit weight inverse minimum‐cost flow problem under the l1 norm reduces to solving a unit capacity minimum‐cost circulation problem, and under the l∞ norm, it reduces to solving a minimum mean cycle problem. We also consider the nonunit weight versions of inverse minimum‐cut and minimum‐cost flow problems under the l∞ norm. © 2002 Wiley Periodicals, Inc.

In this paper we present a theoretical analysis of the deterministic on-line Sum of Squares algorithm (SS) for bin packing, introduced and studied experimentally in [8], along with several new variants.SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB).It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste.For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n).In addition, we present a randomized O(nB log B)-time on-line algorithm SS*, based on SS, whose expected behavior is essentially optimal for all discrete distributions.Algorithm SS* also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste.An off-line randomized variant SS** performs well in a worst-case sense: For any list L of integer-sized items to be packed into bins of a fixed size B, the expected number of bins used by SS** is at most OPT(L) + ~.

The cycle-canceling algorithm is one of the earliest algorithms to solve the minimum-cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting flows along negative-cost directed cycles in the residual network G(x) and thereby canceling them. For the minimum-cost flow problem with integral data, the generic version of the cycle-canceling algorithm runs in pseudopolynomial time, but several polynomial-time specific implementations can be obtained by specifying the choices of cycles to be canceled. In this paper, we describe a new polynomial-time implementation of the cycle-canceling algorithm. Our algorithm is a scaling algorithm and proceeds by augmenting flows along negative cycles with “sufficiently large” residual capacity. Further, it identifies such a cycle by solving a shortest path problem with nonnegative arc lengths. For a network with n nodes and m arcs, our cycle-canceling algorithm performs O(m log(nU)) augmentations and runs in O(m(m + n log n) log (nU)) time, where U is an upper bound on the node supplies/demands and finite arc capacities. We also show that the cycle-canceling algorithm (i) can solve the uncapacitated minimum-cost flow problem in O(n(m + n log n) log (nU)) time; (ii) can obtain an integer optimal solution of the convex cost-flow problem in O(m(m + n log n) log (nU)) time; and (iii) can be modified so that it runs in O(m(m + n log n) min {log (nU), m log n}) time, which is a strongly polynomial time bound. © 2000 John Wiley & Sons, Inc.

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if costs are piecewise linear convex functions of the flow? In this paper, we show that this problem can be solved using $\min\{ m,\log T,\ub{\Gamma}{U} \}$ maximum flow computations and one minimum (convex) cost flow computation. Here m is the number of arcs, $\Gamma$ is the maximum supply or demand, and U is the maximum capacity. When there is only one sink, this problem can be solved in the same asymptotic time as one minimum (convex) cost flow computation. This improves upon the previous best algorithm to solve the problem without costs by a factor of k. Our solutions start with a stationary fractional flow and use rounding to transform this into an integral flow. The rounding procedure takes O(n) time.

The feature article by Reeves presents an excellent survey of genetic algorithms (GAs). It covers the history of GAs and the application of GAs to combinatorial problems, while providing useful background and a balanced operations research (OR) perspective. In this commentary, we hope to complement the survey by focusing on some aspects of GAs that Reeves did not have an opportunity to comment on in depth.

In the mathematical programming literature, researchers have conducted a large number of computational studies to assess the empirical behavior of various algorithms and have utilized CPU time as the primary measure of performance. CPU time has the following drawbacks as a measure of an algorithm's performance: it is implementation dependent, hard to replicate, and limited in the insight it provides into an algorithm's behavior. In this paper, we illustrate the notion of representative operation counts that can complement the conventional CPU time analysis and can help us (i) to identity the asymptotic bottleneck operations in an algorithm, (ii) to estimate an algorithm's running time for different problem sizes, and (iii) to obtain a fairer comparison of several algorithms. These concepts are easily incorporated into empirical studies and often yield valuable insights into an algorithm's behavior.

This is a commentary to the McGeoch's feature article. It focuses on a few aspects of the feature article, primarily from the background of computational tests on network optimization algorithms and on combinatorial optimization algorithms.

Abstract The constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more thanD. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow, and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in O((m log M) S(n, m)) time, wherenis the number of nodes in the network;m, the number of arcs; M, an upper bound on the largest element in the data: and S(n, m), the time required to solve a shortest path problem with nonnegative arc lengths. Our algorithms are generalizations of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.

In this paper, network flow algorithms for bipartite networks are studied. A network $G = (V,E)$ is called bipartite if its vertex set V can be partitioned into two subsets $V_1 $ and $V_2 $ such that all edges have one endpoint in $V_1 $ and the other in $V_2 $. Let $n = |V|$, $n_1 = |V_1 |$ , $n_2 = |V_2 |$, $m = |E|$ and assume without loss of generality that $n_1 \leqslant n_2 $. A bipartite network is called unbalanced if $n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow algorithms can be substantially sped up when applied to unbalanced networks. The basic idea in these improvements is a two-edge push rule that allows one to “charge” most computation to vertices in $V_1 $, and hence develop algorithms whose running times depend on $n_1 $ rather than n. For example, it is shown that the two-edge push version of Goldberg and Tarjan’s FIFO preflow-push algorithm runs in $O(n_1 m + n_1^3 )$ time and that the analogous version of Ahuja and Orlin’s excess scaling algorithm runs in $O(n_1 m + n_1^2 \log U)$ time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.

Abstract Let D = (V, E) be a digraph with n vertices and m arcs. For each e ∈ E there is an associated cost ce and a transit time te; ce can be arbitrary, but we require te to be a non‐negative integer. The cost to time ratio of a cycle C is Λ(C) = ∑e∈cce/∑e∈c. Let E' ⊆ E denote the set of arcs e with te > 0, let Tu = max{tuv: (u, v) ∈ E} for each vertex u, and let T = ∑u∈v Tu. We give a new algorithm for finding a cycle C with the minimum cost to time ratio Λ(C). The algorithm's O(T(m + n lo g n)) running time is dominated by O(T) shortest paths calculations on a digraph with non‐negative arc lengths. Further, we consider early termination of the algorithm and a faster O(Tm) algorithm in case E – E' is acyclic, i.e., in case each cycle has a strictly positive transit time, which gives an O(n2) algorithm for a class of cyclic staffing problems considered by Bartholdi et al. The algorithm can be seen to be an extension of the O(nm) algorithm of Karp for the case in which te = 1 for all e ∈ E, which is the problem of calculating a minimum mean cycle. Our algorithm can also be modified to solve the related parametric shortest paths problem in O(T(m + n log n)) time. © 1993 by John Wiley & Sons, Inc.

Abstract We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm. For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider. An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).

Efficient implementations of Dijkstra's shortest path algorithm are investigated. A new data structure, called the radix heap , is proposed for use in this algorithm. On a network with n vertices, m edges, and nonnegative integer arc costs bounded by C , a one-level form of radix heap gives a time bound for Dijkstra's algorithm of O ( m + n log C ). A two-level form of radix heap gives a bound of O ( m + n log C /log log C ). A combination of a radix heap and a previously known data structure called a Fibonacci heap gives a bound of O ( m + n a @@@@log C ). The best previously known bounds are O ( m + n log n ) using Fibonacci heaps alone and O ( m log log C ) using the priority queue structure of Van Emde Boas et al. [ 17].

Recently, Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in $O(n^3 )$ time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of $O(nm\log (n^2 /m)$ on m-arc networks. Ahuja and Orlin developed a variant of Goldberg’s algorithm that uses scaling and runs in $O(nm + (n^2 \log U)$ time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of $O(nm + n^2 \log U/\log \log U)$ is obtained by using a nonconstant scaling factor. Second, an even better bound of $O(nm + n^2 (\log U)^{1/2} )$ is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to $O(nm\log (({n / m})(\log U)^{{1 / 2}} + 2))$. This result shows that the combined use of three different techniques, results in speed not obtained by using any of the techniques alone. The above bounds are all for a unit-cost random access machine. Also considered is a semilogarithmic computation model in which the bounds increase by an additive term of $O(m\log _n U)$, which is the time needed to read the input in the model.

We present a new strongly polynomial algorithm for the minimum cost flow problem, based on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the uncapacitated minimum cost flow problem as a sequence of Ο(n log n) shortest path problems on networks with n nodes and m arcs and runs in Ο(n log n(m + n log n)) steps. Using a standard transformation, this approach yields an Ο(m log n (m + n log n)) algorithm for the capacitated minimum cost flow problem. This algorithm improves the best previous strongly polynomial algorithm due to Galil and Tardos, by a factor of m/n. Our algorithm is even more efficient if the number of arcs with finite upper bounds, say m', is much less than m. In this case, the number of shortest path problems solved is Ο((m + n) log n).

Abstract We consider a minimum‐cost dynamic network‐flow problem on a very special network. This network flow problem models an infinite‐horizon, lot‐sizing problem with deterministic demand and periodic data. We permit two different objectives: minimize long‐run average‐cost per period and minimize the discounted cost. In both cases we give polynomial algorithms when certain arc costs are fixed charge functions, and others are linear.

Abstract This paper presents and solves in polynomial time the dynamic matching problem, an integer programming problem which involves matchings in a time‐expanded infinite network. The initial model is a finite directed graph G = (V, E) in which each edge has an associated real‐valued weight and an integral distance. We wish to “match” vertices over an infinite horizon, and we permit vertex i in period p to be matched to vertex j in period r if and only if there is an edge e = (i, j) of E with distance r‐p or else an edge e = (j, i) of E with distance p‐r. Equivalently, we construct a “dynamic graph” in which there is an edge incident to vertex i‐p and to vertex j‐r in the above cases. The weight of this matched edge in the dynamic (time‐expanded) graph is the weight of e. The dynamic matching problem is to determine a matching M in the dynamic graph such that M has a maximum long‐run average weight per period. We show that the infinite horizon dynamic matching problem is linearly transformable to the finite horizon Q‐matching problem, which is shown to be solvable in polynomial time in Part II of this paper.

Abstract Consider a directed graph G in which every edge has an associated real‐valued distance and a real‐valued weight. The weight of an undirected circuit of G is the sum of the weights of the edges, whereas the distance of an undirected circuit is the sum of the distances of the forward edges of the circuit minus the sum of the distances of the backward edges. A trivial circuit is a two‐edge circuit in which one edge of G appears twice on the circuit. A quasidynamic fractional matching (or Q‐matching) is a collection of vertex‐disjoint circuits such that each circuit is either trivial or else it is an odd circuit whose distance is nonzero. The G‐matching problem is to find a Q‐matching that maximizes the sum of the weights of its circuits. The Q‐matching problem generalizes both the matching problem and the fractional matching problem. Moreover, the dynamic matching problem, which is a matching problem on an infinite dynamic (time‐expanded) graph, is linearly transformable to the Q‐matching problem, as shown in Part I of this paper. In this paper we solve the Q‐matching problem by generalizing Edmonds' blossom algorithm. In fact, all of the major components of the blossom algorithm‐including alternating trees, augmentations, shrinking, and expanding‐are appropriately generalized to yield a running time that is proportional to that for the weighted matching problem. Furthermore, if all edge distances are equal to zero, this new algorithm reduces to the blossom algorithm.

In this paper we offer a unifying framework for dynamic problems in terms of “dynamic languages”, and we discuss the complexity of these languages. In particular, many dynamic languages derived from NP-complete languages can be shown to be polynomial space (P-space) complete. Among these are the following: the dynamic 3-satisfiability problem, and dynamic 3-dimensional matching problem, the dynamic partition problem, the dynamic hamiltonian circuit problem, and the dynamic independent set problem. We provide a general technique for showing how to prove the P-space completeness of dynamic problems derived from NP-complete problems.