Search

Network Survivability is a critical issue in telecommunication networks due to the increasing dependence of the society on communication systems. Fast restoration from a network failure is an important challenge that deserves attention. This paper addresses an optimal link capacity and flow assignment design problem for survivable asynchronous transfer mode (ATM) network based on two restoration strategies: a path restoration and a link restoration. Given a projected traffic demand and the network topology, capacity and flow assignment are jointly optimized to yield the optimal capacity placement and the flow allocation. The problem is formulated as a large-scale nonconvex nonlinear multicommodity flow problem and is solved by a special augmented Lagrange method (so called Separable Augmented Lagrangian Algorithm or SALA for short). Several networks with diverse topological characteristics are used in the experiments to compare the two restoration strategies. Numerical results have shown that the link restoration strategy requires more capacity than the path restoration strategy in symmetric and asymmetric traffic. The link restoration strategy also increases the routing cost, the capacity installation cost and the total cost.

The Multiplicative Weights Update method (MWU) is a simple yet powerful algorithm for learning linear classifiers, for ensemble learning a la boosting, for approximately solving linear and semidefinite systems, for computing approximate solutions to multicommodity flow problems, and for online convex optimization, among other applications. In this brief announcement, we apply techniques from interactive theorem proving to define and prove correct the first formally verified implementation of MWU (specifically, we show that our MWU is no regret). Our primary application -- and one justification of the relevance of our work to the PODC community -- is to verified multi-agent systems, such as distributed multi-agent network flow and load balancing games, for which verified MWU provides a convenient method for distributed computation of approximate Coarse Correlated Equilibria.

We show the strong-convexity assumption of regularization-based methods for solving bilinear saddle point problems may be relaxed to a weaker notion of area-convexity with respect to an alternating bilinear form. This allows bypassing the infamous '' barrier for strongly convex regularizers that has stalled progress on a number of algorithmic problems. Applying area-convex regularization, we present a nearly-linear time approximation algorithm for solving matrix inequality systems A X ≤ B over right-stochastic matrices X. By combining that algorithm with existing work on preconditioning maximum-flow, we obtain a nearly-linear time approximation algorithm for maximum concurrent flow in undirected graphs: given an undirected, capacitated graph with m edges and k demand vectors, the algorithm takes O(mke'1) time and outputs k flows routing the specified demands with total congestion at most (1+e) times optimal.

Rapid growth in capacity makes flow-based microfluidic biochips a promising candidate for biochemical analysis because they can integrate more complex functions. However, as the number of components grows, the total length of flow channels between components must increase exponentially. Recent empirical studies show that long flow channels are vulnerable due to blocking and leakage defects. Thus, it is desirable to minimize the total length of flow channels for robustness. Also, for timing-sensitive biochemical assays, increase in the longest length of flow channel will delay the assay completion time and lead to variation of fluid, thereby affecting the correctness of outcome. The increasing number of components, including the pre-placed components, on the chip makes the flow channel routing problem even more complicated. In this paper, we propose an efficient obstacle-avoiding rectilinear Steiner minimum tree algorithm to deal with flow channel routing problem in flow-based microfluidic biochips. Based on the concept of Kruskal algorithm and formulating the considerations as a bi-criteria function, our algorithm is capable of simultaneously minimizing the total length and the longest length of flow channel.

In this paper, we present a novel idea to solve maximum flow problem in the directed networks. Given a directed flow network which we call original network here, we propose a method of Contracting Neighbor-node-set Approach (CNA) based on Quotient Space Theory. It selects some nodes from fine-grained original network as equivalence class to form a new node in the new network. The coarse-grained new network is called quotient network. Then we apply classic algorithms on quotient network to solve the maximum flow of original network. The performance in practice of our algorithm is better than that of classic algorithms and the method of simplifying network. Experimental results show that CNA can approximate accurately solve the maximum flow of original network. The correctness of maximum flow is over 95%. At the same time, the node scale reduces to 55.45% of node scale of original network and edge scale reduces to 32.10% of edge scale of original network, averagely.

Original manuscript May 8, 2012, The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a 1-ε approximation to the multicommodity flow problem on graphs is a well-studied problem. In this paper we present an adaptation of recent advances in single-commodity flow algorithms to this problem. As the underlying linear systems in the electrical problems of multicommodity flow problems are no longer Laplacians, our approach is tailored to generate specialized systems which can be preconditioned and solved efficiently using Laplacians. Given an undirected graph with m edges and k commodities, we give algorithms that find 1-ε approximate solutions to the maximum concurrent flow problem and maximum weighted multicommodity flow problem in time O(m[superscript 4/3]poly(k,ε[superscript -1]))., National Science Foundation (U.S.) (Grant CCF-1018463), National Science Foundation (U.S.) (Award 0843915), National Science Foundation (U.S.) (Award 1111109), Microsoft Corporation (Fellowship)

Suppose we are given a graph G = (V, E) and a set of terminals K ⊂ V. We consider the problem of constructing a graph H = (K, E[subscript H]) that approximately preserves the congestion of every multicommodity flow with endpoints supported in K. We refer to such a graph as a flow sparsifier. We prove that there exist flow sparsifiers that simultaneously preserve the congestion of all multicommodity flows within an O(log k / log log k)-factor where |K| = k. This bound improves to O(1) if G excludes any fixed minor. This is a strengthening of previous results, which consider the problem of finding a graph H = (K, E[subscript H]) (a cut sparsifier) that approximately preserves the value of minimum cuts separating any partition of the terminals. Indirectly our result also allows us to give a construction for better quality cut sparsifiers (and flow sparsifiers). Thereby, we immediately improve all approximation ratios derived using vertex sparsification in [14]. We also prove an Ω(log log k) lower bound for how well a flow sparsifier can simultaneously approximate the congestion of every multicommodity flow in the original graph. The proof of this theorem relies on a technique (which we refer to as oblivious dual certifcates) for proving super-constant congestion lower bounds against many multicommodity flows at once. Our result implies that approximation algorithms for multicommodity flow-type problems designed by a black box reduction to a "uniform" case on k nodes (see [14] for examples) must incur a super-constant cost in the approximation ratio.

This paper addresses a fundamental issue in the multicommodity flow theory. For an undirected capacitated supply graph (G,c) having commodity graph H, the maximum multiflow problem is to maximize the total flow-value of multicommodity flows with respect to (G,c;H). For a commodity graph H, the fractionality of H is the least positive integer k with property that there exists a 1/k-integral optimal multiflow in the maximum multiflow problem for every integer-capacitated supply graph (G,c) having H as a commodity graph. If such a positive integer k does not exist, then the fractionality is defined to be infinity. Around 1990, Karzanov raised the problem of classifying commodity graphs with finite fractionality, gave a necessary condition (property P) for the finiteness of fractionality, and conjectured that the property P is also sufficient. Our main result affirmatively solves Karzanov's conjecture in algorithmic form: If H has property P, then there exists a 1/24-integral optimal multiflow in maximum multiflow problem for every integer-capacitated supply graph having H as a commodity graph, and there exists a strongly polynomial time algorithm to find it. Our proof is based on a special combinatorial duality relation involving a class of CAT(0) complexes, and on a fractional version of the splitting-off method for finding an optimal multiflow with a bounded denominator.

This paper studies maximum multicommodity flow and maximum concurrent flow in multihop wireless networks subject to both bandwidth and interference constraints. The existing proof of the NP-hardness of both problems is too contrived to be applicable to meaningful multihop wireless networks. In addition, all known constant-approximation algorithms for both problems restricted to various network classes are super-exponential in running time. Some of them are simply incorrect. In this paper, we first provide a rigorous proof of the NP-hardness of both problems even in very simple settings. Then, we show that both problems restricted to a broad family of multihop wireless networks admit polynomial-time approximation scheme (PTAS). After that, we develop a unified framework for the design and analysis of polynomial approximation algorithms for both problems. Following such framework, we obtain polynomial constant-approximation algorithms for both problems restricted to a broad network family. The approximation ratios of these algorithms are also better than those known in the literature.

We consider the fair multicommodity flow problem in multihop wireless networks. We optimize the flow between a number of source-destination pairs to achieve a fair allocation of network resources while satisfying node capacity constraints. To account for the limitations of wireless devices, we use a path-based formulation and allow only a bounded number of paths between each source-destination pair. We develop a dual decomposition based distributed algorithm for solving the problem, show the optimality of a stationary solution, and compare the performance of the algorithm with a centralized branch-and-bound method.

We consider solutions for distributed unsplittable multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. A requirement here is that each commodity routes its entire demand along a single path at any point in time. Assuming that the minimum capacity of any edge is at least polylogarithmic factor larger than the maximum demand of any commodity, we present a greedy distributed randomized algorithm, which with high probability, achieves 1+e approximation, in O(H · logO(1)) m · (1/e)0(1)) iterations where H ≤ n is an upper bound on the number edges allowed on any flow-path. No prior results exist for our distributed model.Our algorithm is based on simulating the splittable multicommodity flow solution of [1] and picking a path for routing the entire flow according to the probability distribution given by the splittable flow. We use Chernoff bounds to show that the real edge-congestions are sufficiently close to the edge-congestions in the simulation for the analysis of [1] to hold.

This article analyzes the problem of optimizing access to and transport of large remote data through intelligent resource selection and configuration. With the availability of high speed optical networks, the main problem for remote data access is shifting from having enough network bandwidth to having enough data ready to saturate the network when requested by the application. Network bandwidth is now higher than disk bandwidth and this gives us the possibility of utilizing multiple distributed resources to saturate the network links. We are considering two types of scenarios, one where we use only disks as data sources and a more advanced scenario where compute resources in the network can be utilized as caches to increase instantaneous throughput.The problem we are facing is choosing and configuring the resources for this scenario. This is a non-trivial problem however as we are using application-driven network resource allocation (which gives us predictability and determinism in terms of network performance) the problem becomes tractable. We discuss optimization algorithms that are applicable to this problem, and present an algorithm that divides the problem in two sub-problems that can be solved using existing network flow algorithms.

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other: • Passive Commodity Monitoring: minimize the total cost of monitoring devices used to measure the network traffic on all paths.• Maximum Throughput Multicommodity flow: maximize the total value of the flow with bounded edge capacities..We present the first known distributed algorithms for both of these problems that converge to (1+e)-approximate solutions in poly-logarithmic time with communication and space overheads that depend on the maximal path length but are almost independent of the size of the entire network. Previous distributed solutions achieving similar approximations required convergence time, communication, or space overheads that depend polynomially on the size of the entire network. The sequential simulation of our algorithm is more efficient than the fastest known approximation algorithms for multicommodity flows, e.g., Garg-Konemann [14], when the maximal path length is small.

We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given ann-vertex graphGalong withksource-sink pairs, and the goal is to find the minimum cardinality subset of edges whose removal separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of the number of deleted edges to the number of source-sink pairs that are separated by this deletion. The natural linear programming relaxation for multicut corresponds, by LP-duality, to the well-studied maximum (fractional) multicommodity flow problem, while the standard LP-relaxation for sparsest cut corresponds to maximum concurrent flow. Therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also theflow-cut gap: the largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem.Our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is Ω˜(n1/7) in directed graphs. We show a similar result for the gap between maximum concurrent flow and sparsest cut in directed graphs. These results improve upon a long-standing lower bound of Ω(logn) for both types of flow-cut gaps. We notice that these polynomially large flow-cut gaps are in a sharp contrast to the undirected setting where both these flow-cut gaps are known to be Θ(logn). Our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2Ω(log1-ϵn)for any constant ϵ > 0, unless NP ⊆ ZPP. This improves upon the recent Ω(logn/log logn)-hardness result for these problems. We also show that existence of PCP's for NP with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems. All our results hold for directed acyclic graphs.

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an NΩ(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have NO(log logN)-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor NO(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of NΩ(1/c) for c ranging from 1 to Θ((log n)/(log log n)).A solution to the routing problem involves selecting which pairs tobe routed and what paths to assign to each routed pair. Two naturalrestrictions can be placed on input instances to eliminate one ofthese aspects of the problem complexity. The first restriction is toconsider instances with perfect completeness; an optimalsolution is able to route all pairs with congestion 1 in suchinstances. The second restriction to consider is the uniquepaths property where each source-destination pair has a unique pathconnecting it in the instance. An important aspect of our result isthat it holds on instances with any one of these tworestrictions. Our hardness construction with the perfectcompleteness restriction allows us to conclude that the directedcongestion minimization problem, where the goal is to route allpairs with minimum congestion, is hard to approximate to within afactor of Ω(log N/log log N). On the other hand, thehardness construction with unique paths property allows us toconclude an NΩ(1/c) inapproximability bound also for theall-or-nothing flow problem. This is in a sharp contrast to theundirected setting where the all-or-nothing flow problem is known tobe approximable to within a poly-logarithmic factor.

Designing and planning of the switching, signaling and support network is a fairly complex process in cellular mobile network. In this paper, the problem of assigning cells to switches in cellular mobile network, which is considered a planning problem, is addressed. The cell to switch assignment problem which falls under the category of the Quadratic Assignment Problem (QAP) is a proven NP--hard problem. Further, the problem is modeled to include an additional constraint in the formulation. The additional constraint is of the maximum number of switch ports that are used for a cell's Base Station Transceiver System (BTS) connectivity to the switch. The addition of the constraint on the number of ports on a switch has immense practical significance. This paper presents a non--deterministic heuristic based on Simulated Evolution (SimE) iterative algorithm to provide solutions. The methods adopted in this paper are a completely innovative formulation of the problem and involve application of Evolutionary Computing for this complex problem that may be extended to solutions of similar problems in VLSI design, distributed computing and many other applications.

We study the approximability of the multicut and the (non-bipartite) sparsest cut problems in directed graphs. In the multicut problem, we are a given a graph G along with k source-sink pairs, and the goal is to find a smallest subset of edges whose deletion separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of deleted edges to the number of source-sink pairs that are separated by this deletion. Study of algorithms for cut problems is intimately connected to the dual notion of flows in networks, and many approximation algorithms for cut problems use a flow solution as a starting point. The best known approximation algorithm for directed multicut is based on this approach and gives an O(√n)-approximation. On the other hand, the gap between the maximum multicommodity flow and the minimum multicut is known to be Ω(min(k , log n)). While this flow-cut gap may be interpreted as an evidence of inherent difficulty in designing good approximation algorithms for directed multicut, the strongest hardness result known is an APX-hardness. Even assuming the Unique Games Conjecture, only an ω(1)-hardness is known. Similar bounds hold for the directed sparsest cut problem.Our main result is that directed multicut is Ω(log n / log log n)-hard to approximate unless NP ⊆ DTIME (npolylog n). We show that this hardness result holds even when we allow a bicriteria relaxation, where the approximate solution is required to separate only a constant fraction of the pairs. This bicriteria hardness allows us to infer an Ω(log n / log log n)-hardness for the directed (non-bipartite) sparsest cut problem.

The set covering problem and the minimum cost assignment problem (respectively known as unate and binate covering problem) arise throughout the logic synthesis flow. This paper investigates the complexity and approximation ratio of two lower bound computation algorithms from both a theoretical and practical point of view. It also presents a new pruning technique that takes advantage of the partitioning.

We show that there is no log 1 over 3-eM approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME(npolylog(n), where M is the size of the graph and e is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.

We study multicommodity routing problems in both edge and node capacitated undirected graphs. The input to each problem is a capacitated graph G=(V,E) and a set Τ of node pairs. In the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. If we allow fractional routings of the flow, it is known as the all-or-nothing flow problem. The nodes in Τ are referred to as terminals.In recent work [8,9], the authors obtained the first poly-logarithmic approximation algorithms for some edge routing problems. A key idea in these algorithms is to decompose an instance into a collection of instances in which the terminals are well-linked. Informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. A decomposition into well-linked instances was previously achieved in [8] via racke's hierarchical graph decomposition for oblivious routing [32]. In this paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. Our new algorithm improves the earlier results for edge routing problems. Another important advantage of the algorithm is that it also applies to node-capacitated problems. We note that for oblivious routing with node capacities, an Ω√n) lower bound is known on the congestion [18], and hence the oblivious routing approach cannot yield poly-logarithmic bounds for well-linked decompositions. Using the new decomposition, we obtain a poly-logarithmic approximation for the node capacitated all-or-nothing flow problem in general graphs and node-disjoint path problem in planar graphs with O(1) congestion. We also show that the flow-cut gap for product multicommodity flows in node capacitated planar graphs is O(1), improving upon the O(log n) bound from [28].

To deliver quality of service, internet service providers are seeking effective solutions to optimize their networks. One of the main tasks is to optimally route a set of traffic demands, each along a single path, while satisfying their bandwidth requirements and without exceeding edge capacities. This is an integer multicommodity flow problem, which is known to be NP-hard. To solve this problem efficiently, a new complete and scalable hybrid solver (HLR) integrating Lagrangian relaxation and constraint programming has been proposed. It exploits the shortest path decomposition of the problem and has been shown to yield significant benefits over several other algorithms, such as CPLEX and well-known routing heuristics. In this paper we explore an alternative dualization within the same hybrid. We present a variant of HLR, adapted to the knapsack decomposition of the problem. Although this relaxation seems less natural, experimental results show that it has some advantages. The paper provides an interesting insight of where the benefits may lie, in particular for larger and harder cases where the ratio of total demand to available capacity is higher.

In this paper, we examine the problem of large-volume data dissemination via overlay networks. A natural way to maximize the throughput of an overlay multicast session is to split the traffic and feed them into multiple trees. While in single-tree solutions, bandwidth of leaf nodes may remain largely under-utilized, multi-tree solutions increase the chances for a node to contribute its bandwidth by being a relaying node in at least one of the trees. We study the following problems: (1) What is the maximum capacity multi-tree solutions can exploit from overlay networks? (2) When multiple sessions compete within the same network, what is the relationship of two contradictory goals: achieving fairness and maximizing overall throughput? (3) What is the impact of IP routing in achieving at constraining the optimal performance of overlay multicast.We extend the multicommodity flow model to the case of overlay data dissemination, where each commodity is associated with an overlay session, rather than the traditional source-destination pair. We first prove that the problem is solvable in polynomial time, then propose an e-approximation algorithm, assuming that each commodity can be split in arbitrary ways. The solution to this problem establishes the theoretical upper bound of overall throughput that any multi-tree solution could reach. We then study the same problem with the restriction that each commodity can only be split and fed into a limited number of trees. A randomized rounding algorithm and an online tree-construction algorithm are presented. All these algorithms are evaluated by extensive simulations.

We consider the all-or-nothing multicommodity flow problem in general graphs. We are given a capacitated undirected graph $G=(V,E,u)$ and a set of $k$ node pairs $s_1 t_1, s_2t_2, \ldots ,s_kt_k$. Each pair has a unit demand. A subset $S$ of $\{1,2,\ldots,k\}$ is routable if there is a multicommodity flow in $G$ that simultaneously sends one unit of flow between $s_i$ and $t_i$ for each $i$ in $S$. Note that this differs from the edge-disjoint path problem (edp) in that we do not insist on integral flows for the pairs. The objective is to find a maximum routable subset $S$. When $G$ is a capacitated tree, the problem already generalizes $b$-matchings, and even in this case it is NP-hard and APX-hard to approximate. For trees, a $2$-approximation is known for the cardinality case and a $4$-approximation for the weighted case. In this paper we show that the natural linear programming relaxation for the all-or-nothing flow problem has a polylogarithmic integrality gap in general undirected graphs. This is in...

We adapt a method proposed by Nesterov [16] to design an algorithm that computes e-optimal solutions to fractional packing problems by solving O*(e-1 √Kn) separable convex quadratic programs, where K is the maximum number of non-zeros per row and n is the number of variables. We also show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. For the special case of the maximum concurrent flow problem on a graph G =(V,E) with rational capacities and demands we obtain an algorithm that computes an E-optimal flow by solving O*(e-1K3/2|E| √|V| (log 1/e+ LU + LD)) shortest path problems, where K is the number of commodities, and LU, LD are, respectively, the number of bits needed to store the capacities and demands. We also show that the complexity of computing a maximum multicommodity flow is O*(1/elog2(1/e)). In contrast, previous algorithms required Ω(e-2) iterations.

It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees du and dv we have O(du dv) units of demand. Thus the total demand is O(n2). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O(n log2 n). This is to be compared with a bound O(n2) that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.

In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based. We consider the single-commodity confluent flow problem, in which we are given an n-node directed network G, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge (and node) congestion O(C^2log^3n), where C is the node congestion of a splittable flow with minimum node congestion; here the node congestion of a flow is the maximum, over all nodes other than t, of the congestion at a node. This implies an [email protected]?(n) approximation algorithm for the problem with uniform supplies. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest. For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 32. We also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems.

Racke recently gave a remarkable proof showing that any undirected multicommodity flow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log3 n) of the best off-line solution to the problem. He also presented interesting applications of this result to distributed computing. Maggs, Miller, Parekh, Ravi and Wu have shown that such a decomposition also has an application to speeding up iterative solvers of linear systems. Racke's construction finds a decomposition tree of the underlying graph, along with a method to obliviously route in a hierarchical fashion on the tree. The construction, however, uses exponential-time procedures to build the decomposition. The non-constructive nature of his result was remedied, in part, by Azar, Cohen, Fiat, Kaplan, and Racke, who gave a polynomial time method for building an oblivious routing strategy. Their construction was not based on finding a hierarchical decomposition, and this precludes its application to iterative methods for solving linear systems. In this paper, we show how to compute a hierarchical decomposition and a corresponding oblivious routing strategy in polynomial time. In addition, our decomposition gives an improved competitive ratio for congestion of O(log2n log log n). In an independent result in this conference, Bienkowski, Korzeniowski, and Racke give a polynomial-time method for constructing a decomposition tree with competitive ratio O(log4n). We note that our original submission used essentially the same algorithm, and we appreciate them allowing us to present this improved version.

We consider the problem of determining rates of growth for the maximum stable throughput achievable in dense wireless networks. We formulate this problem as one of finding maximum flows on random unit-disk graphs. Equipped with the max-flow/min-cut theorem as our basic analysis tool, we obtain rates of growth under three models of communication: (a) omnidirectional transmissions; (b) "simple" directional transmissions, in which sending nodes generate a single beam aimed at a particular receiver; and (c) "complex" directional transmissions, in which sending nodes generate multiple beams aimed at multiple receivers. Our main finding is that an increase of Θlog2n in maximum stable throughput is all that can be achieved by allowing arbitrarily complex signal processing (in the form of generation of directed beams) at the transmitters and receivers. We conclude therefore that neither directional antennas, nor the ability to communicate simultaneously with multiple nodes, can be expected in practice to effectively circumvent the constriction on capacity in dense networks that results from the geometric layout of nodes in space.

We show how that new approximation algorithms by Garg and Konemann for the multicommodity flow problem can be modified to solve the linear programming relaxation of the global routing problem. The algorithm presented here also provides a solution of the dual linear problem, thus gives a lower bound on the optimum maximum relative congestion. Our computation results with recent IBM processor chips show that this approach can be used in practice even for large chips and that it is superior on difficult instances where rip-up and reroute algorithms fail.

We propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). Despite a rich history dating back to Kantorovich and Dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. Polynomial combinatorial algorithms were previously known only for the version of our problem without costs. We design the first such algorithms for the version with costs. Our algorithms also find provably good solutions faster than optimal ones, providing the first strongly polynomial approximation schemes for the problem. Our techniques extend to optimize linear programs with two variables per inequality. Polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. We propose the first such methods for the optimization version.