We consider multicommodity flows in undirected graphs. An instance consists of an edgecapacitated graph \(G\), called the supply graph, and a set of source-sink pairs with associated demands (commodities), defining a demand graph \(H\). An instance is said to be feasible if there exists a flow that routes all demands while respecting the edge capacities. In many applications, it is further required that the entire demand of each commodity be routed along a single path; this is known as the unsplittable multicommodity flow problem. We study conditions under which the existence of a feasible (splittable) flow implies the existence of an unsplittable flow that does not significantly violate edge capacities.

Submodular function maximization has found a wealth of new applications in recent years. The related supermodular maximization models also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems.

Gomory--Hu (GH) trees are a classical sparsification technique for graph connectivity. For an edge-capacitated undirected graph $G=(V,E)$ and subset $Z \subseteq V$ of terminals, a GH tree is an edge-capacitated tree $T=(Z,E(T))$ such that for every $u,v \in Z$, the value of the minimum capacity $uv$ cut in $G$ is the same as in $T$. It is well-known that there does not always exist a GH tree which is a subgraph (or minor if $Z \neq V$) of $G$. We characterize those graph-terminal pairs $(G,Z)$ which always admit such a tree. We show that these are the graphs which have no terminal-$K_{2,3}$ minor, that is, a $K_{2,3}$ minor whose nodes each corresponds to a terminal. We then show that the pairs $(G,Z)$ which forbid such $K_{2,3}$ terminal-minors arise, roughly speaking, from so-called Okamura--Seymour instances, planar graphs whose outside face contains all terminals. One consequence is a result on cut-sufficient pairs $(G,H)$, that is, multiflow instances where the cut condition is sufficient to guarantee a multiflow for any capacity/demand weights on $G/H$. Our results characterize the pairs $(G,Z)$ where $G$ is a graph, $Z \subseteq V(G)$, such that $(G,H)$ is cut-sufficient for any demand graph $H$ on $Z$.

The multilinear framework was developed to achieve the breakthrough 1 – 1/e approximation for maximizing a monotone submodular function subject to a matroid constraint, which includes the submodular welfare problem as special case. This framework has a continuous optimization part (solving the multilinear extension of a submodular set function) and a rounding part (rounding a fractional solution to an integral one). We extend both parts so that the resulting generalized framework may be used on a wider array of problems. In particular, we make a conceptual contribution by identifying a family of parameterized functions and their applications. As a running example we focus on solving diversity problems max , where ℳ is matroid. These diversity functions have Aij ≥ 0 as a measure of dissimilarity of i, j, and A has 0-diagonal. This family of problems ranges from intractable problems such as densest k-subgraph, to ½-approximable metric diversity problems. The multilinear extension F of such diversity functions satisfies ▿2F(x) = A ≥ 0 and hence the original multilinear framework (which assumes non-positive Hessians) does not directly apply. Instead we introduce a new parameter for functions F ∊ C2 which measures the approximability of the associated problem max{F(x) : x ∊ P}, for solvable downwards-closed polytopes P. A function F is called one-sided σ-smooth if for all u, x ≥ 0, x = 0. For σ = 0 this class includes previously studied classes such as continuous DR-submodular functions, and much more. For the multlinear extension of a diversity function, we show that it is one-sided σ-smooth whenever Aij forms a σ-semi-metric. We give an Ω(1/σ)-approximation for the continuous maximization problem of monotone, normalized one-sided σ-smooth F with an additional property: non-positive third order partial derivatives. Since the multilinear extension of a diversity function has this additional property we can apply the extended multilinear framework to this family of discrete problems. This requires new matroid rounding techniques for quadratic objectives. The result is an Ω(1/σ3/2)-approximation for maximizing a σ-semi-metric diversity function subject to matroid constraint. This improves upon the previous best bound of Ω(1/σ) and we give evidence that it may be tight. For general one-sided smooth functions, we show the continuous process gives an Ω(1/32σ)-approximation, independent of n. In this setting, by discretizing, we present a concrete poly-time algorithm for multilinear functions that satisfy the one-sided σ-smoothness condition.

Submodular functions have found a wealth of new applications in data science and machine learning models in recent years. This has been coupled with many algorithmic advances in the area of submodular optimization: (SO) $\min/\max f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. In this work we focus on a more general class of multivariate submodular optimization (MVSO) problems: $\min/\max f (S_1,S_2,\ldots,S_k): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote union of disjoint sets and hence this model is attractive where resources are being allocated across $k$ agents, who share a “joint” multivariate nonnegative objective $f(S_1,S_2,\ldots,S_k)$ that captures some type of submodularity (i.e. diminishing returns) property. We provide some explicit examples and potential applications for this new framework. For maximization, we show that practical algorithms such as accelerated greedy variants and distributed algorithms achieve good approximation guarantees for very general families (such as matroids and $p$-systems). For arbitrary families, we show that monotone (resp. nonmonotone) MVSO admits an $\alpha (1-1/e)$ (resp. $\alpha \cdot 0.385$) approximation whenever monotone (resp. nonmonotone) SO admits an $\alpha$-approximation over the multilinear formulation. This substantially expands the family of tractable models. On the minimization side we give essentially optimal approximations in terms of the curvature of $f$.

Recent years have seen many algorithmic advances in the area of submodular optimization: (SO) $\min/\max~f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow \mathbb{R}$ is submodular. This progress has been coupled with a wealth of new applications for these models. Our focus is on a more general class of \emph{multi-agent submodular optimization} (MASO) which was introduced by Goel et al. in the minimization setting: $\min \sum_i f_i(S_i): S_1 \uplus S_2 \uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ to denote disjoint union and hence this model is attractive where resources are being allocated across $k$ agents, each with its own submodular cost function $f_i()$. In this paper we explore the extent to which the approximability of the multi-agent problems are linked to their single-agent {\em primitives}, referred to informally as the {\em multi-agent gap}. We present different reductions that transform a multi-agent problem into a single-agent one. For maximization we show that (MASO) admits an $O(α)$-approximation whenever (SO) admits an $α$-approximation over the multilinear formulation, and thus substantially expanding the family of tractable models. We also discuss several family classes (such as spanning trees, matroids, and $p$-systems) that have a provable multi-agent gap of 1. In the minimization setting we show that (MASO) has an $O(α\cdot \min \{k, \log^2 (n)\})$-approximation whenever (SO) admits an $α$-approximation over the convex formulation. In addition, we discuss the class of "bounded blocker" families where there is a provably tight O$(\log n)$ gap between (MASO) and (SO).

A single-sink confluent flow is a routing of multiple demands to a sink r such that any flow exiting a node v must use a single arc. Hence, a confluent flow routes on a tree within the network. In uncapacitated (or uniform-capacity) networks, there is an O(1)-approximation algorithm for demand maximization and a logarithmic approximation algorithm for congestion minimization [6]. We study the case of capacitated networks, where each node v has its own capacity μ(v). Indeed, it was recently shown that demand maximization is in approximable to within polynomial factors in capacitated networks [20]. We circumvent this lower bound in two ways. First, we prove that there is a polylogarithmic approximation algorithm for demand maximization in networks that satisfy the ubiquitous no-bottleneck assumption (NBA). Second, we show a bicriteria result for capacitated networks without the NBA: there is a polylog factor approximation guarantee for demand maximization provided we allow congestion 2. We model the capacitated confluent flows problem using a multilayer linear programming formulation. At the heart of our approach for demand maximization is a rounding procedure for flows on multilayer networks which can be viewed as a proposal algorithm for an extension of stable matchings. In addition, the demand maximization algorithms require, as a subroutine, an algorithm for approximate congestion minimization in a special class of capacitated networks that may be of independent interest. Specifically, we present a polylogarithmic approximation algorithm for congestion minimization in monotonic networks - those networks with the property that μ(u) ≤ μ(v) for each arc (u, v).

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on one of two models. First, design the network for the known point-to-point peak demands. Second, design the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). Both models may be too conservative if additional information on traffic patterns is available. We introduce a capped hose model to explore a range of traffic scenarios, which includes the above two as special cases. It is known that optimal network designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We demonstrate that a wider variety of routing templates is required to address the broader spectrum of capped hose matrices. We propose the use of hierarchical multihub routing templates, a generalization of hub and tree routing. Our empirical analysis is based on a heuristic for the resulting robust network design problem. These lead to two important findings: 1) designs based on multihub routing are often preferable to both hub and shortest path; 2) it may be possible for a carrier to sample their traffic in order to determine which type of routing is most cost-effective for their network.

We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow based relaxation for it. The integrality gap is known to be \(\Omega(\sqrt{n})\) even for planar graphs [11] due to a simple topological obstruction and a major focus, following earlier work [14], has been understanding the gap if some constant congestion is allowed. In planar graphs the integrality gap is O (1) with congestion 2 [19,5]. In general graphs, recent work has shown the gap to be O (polylog( n )) [8,9] with congestion 2. Moreover, the gap is Ω(log Ω( c ) n ) in general graphs with congestion c for any constant c ≥ 1 [1]. It is natural to ask for which classes of graphs does a constant-factor constant-congestion property hold. It is easy to deduce that for given constant bounds on the approximation and congestion, the class of “nice” graphs is minor-closed. Is the converse true? Does every proper minor-closed family of graphs exhibit a constant-factor constant-congestion bound relative to the LP relaxation? We conjecture that the answer is yes. One stumbling block has been that such bounds were not known for bounded treewidth graphs (or even treewidth 3). In this paper we give a polytime algorithm which takes a fractional routing solution in a graph of bounded treewidth and is able to integrally route a constant fraction of the LP solution’s value. Note that we do not incur any edge congestion. Previously this was not known even for series parallel graphs which have treewidth 2. The algorithm is based on a more general argument that applies to k -sums of graphs in some graph family, as long as the graph family has a constant-factor constant-congestion bound. We then use this to show that such bounds hold for the class of k -sums of bounded genus graphs. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices in order to see which traffic models are more shortest path-like as opposed to hub-like. To address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design (RND) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical RND problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands. This study also reveals conditions under which multi-hub routing gives improvements over single-hub and shortest-path routings.

In the d-dimensional bin packing problem (VBP), one is given vectors x1,x2, ... ,xn ∈ Rd and the goal is to find a partition into a minimum number of feasible sets: {1,2 ... ,n} = ∪is Bi. A set Bi is feasible if ∑j ∈ Bi xj ≤ 1, where 1 denotes the all 1's vector. For online VBP, it has been outstanding for almost 20 years to clarify the gap between the best lower bound Ω(1) on the competitive ratio versus the best upper bound of O(d). We settle this by describing a Ω(d1-ε) lower bound. We also give strong lower bounds (of Ω(d1/B-ε) ) if the bin size B ∈ Z+ is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B; we show an upper bound whose exponent is additively "shifted by 1" from the lower bound exponent.

We consider the following network design problem. We are given an undirected graph G = ( V , E ) with edge costs c ( e ) and a set of terminal nodes W ⊆ V . A hose demand matrix is any symmetric matrix D , indexed by the terminals, such that for each i ∈ W , ∑ j≠i D ij ≤ 1. We must compute the minimum-cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An oblivious routing template, in this context, is a simple path P ij for each pair i,j ∈ W . Given such a template, if we are to route a demand matrix D , then for each i,j , we send D ij units of flow along each P ij . Fingerhut et al. [1997] and Gupta et al. [2001] obtained a 2-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured [Italiano et al. 2006] that this solution actually results in the optimal capacity for the single-path VPN design problem; this has become known as the VPN Conjecture . The conjecture has previously been proven for some restricted classes of graphs [Fingerhut et al. 1997; Fiorini et al. 2007; Grandoni et al. 2008; Hurkens et al. 2007]. Our main theorem establishes that this conjecture is true in general graphs. This also has the implication that the single-path VPN problem is solvable in polynomial time. A natural fractional version of the conjecture had also been proposed [Hurkens et al. 2007]. In this version, the routing may split flow between many paths, in specified proportions. We demonstrate that this multipath version of the conjecture is in fact false. The multipath and single path versions of the VPN problem are essentially direct analogues of the randomized and nonrandomized versions of oblivious routing schemes for minimizing congestion for permutation routing [Borodin and Hopcroft 1982; Valiant 1982].

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 sharp contrast to edp, where the gap is known to be $\Theta(\sqrt{n})$; this ratio is also the best approximation ratio currently known for edp. Our algorithm extends to the case where each pair $s_it_i$ has a demand $d_i$ associated with it and we need to completely route $d_i$ to get credit for pair $i$; we assume that the maximum demand of the pairs is at most the minimum capacity of the edges. We also consider the online admission control version where pairs arrive online and the algorithm has to decide immediately on its arrival whether to accept it and the accepted pairs have to be routed. We obtain a randomized algorithm which has a polylogarithmic competitive ratio for maximizing throughput of the accepted requests if it is allowed to violate edge capacities by a $(2+\epsilon)$ factor.

We study the maximum edge-disjoint path problem (MEDP) in planar graphs. We are given a set of terminal pairs and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by edge-disjoint paths. It is well-known that there is an integrality gap of order square root of the number of nodes for this problem even on a grid-like graph, and hence in planar graphs (Garg et al.). In contrast, Chekuri et al. show that for planar graphs, if LP is the optimal solution to the natural linear programming relaxation for MEDP, then there is a subset of size OPT over the logarithm of the number of nodes which is routable with congestion 2. Subsequently they showed that it is possible to get within a constant factor of the optimal solution with congestion 4 instead of 2. We strengthen this latter result to show that a constant approximation is possible also with congestion 2 (and this is tight via the integrality gap grid example). We use a basic framework from work by Chekuri et al. At the heart of their approach is a 2-phase algorithm that selects an Okamura-Seymour instance. Each of their phases incurs a factor 2 congestion. It is possible to reduce one of the phases to have congestion 1. In order to achieve an overall congestion 2, however, the two phases must share capacity more carefully. For the Phase 1 problem, we extract a problem called rooted clustering that appears to be an interesting problem class in itself.

Consider a routing problem instance consisting of a demand graph H = (V, E(H)) and a supply graph G = (V, E(G)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K2, 3. In this paper we are primarily interested in the “integer” flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We formulate a conjecture that states that the integer flow-cut gap is quantitatively related to the fractional flow-cut gap. In particular this strengthens the well-known conjecture that the flow-cut gap in planar and minor-free graphs is O(1) [12] to suggest that the integer flow-cut gap is O(1). We give several technical tools and results on non-trivial special classes of graphs to give evidence for the conjecture and further explore the “primal” method for understanding flow-cut gaps; this is in contrast to and orthogonal to the highly successful metric embeddings approach. Our results include the following: Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a compliant instance and G + H is Eulerian, then an integral routing of H exists. This result includes, as a special case, routing on a ring, but is not a special case of the Okamura-Seymour theorem. Using the above result, we show that the integer flow-cut gap in series-parallel graphs is 5. The integer flow-cut gap in k-Outerplanar graphs is cO(k) for some fixed constant c. A simple proof that the flow-cut gap is O(log k*) where k* is the size of a node-cover in H; this was previously shown by Günlük via a more intricate proof [11].

We consider robust network design problems where the set of feasible demands may be given by an arbitrary polytope or convex body more generally. This model, introduced by Ben-Ameur and Kerivin [2], generalizes the well studied virtual private network (VPN) problem. Most research in this area has focused on finding constant factor approximations for specific polytope of demands, such as the class of hose matrices used in the definition of VPN. As pointed out in [4], however, the general problem was only known to be APX-hard (based on a reduction from the Steiner tree problem). We show that the general robust design is hard to approximate to within polylogarithmic factors. We establish this by showing a general reduction of buy-at-bulk network design to the robust network design problem. In the second part of the paper, we introduce a natural generalization of the VPN problem. In this model, the set of feasible demands is determined by a tree with edge capacities; a demand matrix is feasible if it can be routed on the tree. We give a constant factor approximation algorithm for this problem that achieves factor 8 in general, and 2 for the case where the tree has unit capacities.

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) $s_1t_1$, $s_2t_2$, $\dots$, $s_kt_k$, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an $\Omega(\sqrt{n})$ integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion $c>1$, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an $O(\log n)$ approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an $O(1)$ approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura–Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation.

We consider the following network design problem. We are given an undirected graph G=(V,E) with edges costs c(e) and a set of terminal nodes W. A hose demand matrix for W is any symmetric matrix [Dij] such that for each i, ∑ j ≠ i Dij ≤ 1. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network.

A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of k edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every $2k$–edge-connected graph has k edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding k edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans and Williamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems.

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against edge or node failures in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures, is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case, and an O(log3n) approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems.

A d-furcated flow is a network flow whose support graph has maximum out degree d. Take a single-sink multi-commodity flow problem on any network and with any set of routing demands. Then we show that the existence of feasible fractional flow with node congestion one implies the existence of a d-furcated flow with congestion at most 1+1/(d-1), for d ≥ 2. This result is tight, and sothe congestion gap for d-furcated flows is bounded andexactly equal to 1+ 1/(d-1). For the case d=1 (confluent flows), it is known that the congestion gap is unbounded, namely Θ(log n). Thus, allowing single-sink multicommodity network flows to increase their maximum out degree from one to two virtually eliminates this previously observed congestion gap.

Abstract The authors settle the complexity status of the robust network design problem in undirected graphs. The fact that the flow‐cut gap in general graphs can be large, poses some difficulty in establishing a hardness result. Instead, the authors introduce a single‐source version of the problem where the flow‐cut gap is known to be one. They then show that this restricted problem is coNP‐Hard. This version also captures, as special cases, the fractional relaxations of several problems including the spanning tree problem, the Steiner tree problem, and the shortest path problem. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 50–54 2007

We consider requests for capacity in a given tree network T = ( V , E ) where each edge e of the tree has some integer capacity u e . Each request f is a node pair with an integer demand d f and a profit w f which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b -matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand d max is at most the minimum edge capacity u min , we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.

We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e.g., autonomous systems, enterprise networks, residential customers). This system is at the heart of Internet connectivity. In our model we are given a network topology of nodes and links where the nodes (modeling the various Internet entities) act as the players of the game, and links represent potential contracts. Nodes wish to satisfy their demands, which earn potential revenues, but nodes may have to pay (or be paid by) their neighbors for links incident to them. By incorporating some of the qualities of Internet business relationships, we hope that our model has predictive value. Specifically, we assume that contracts are either customer-provider or peering contracts. As often occurs in practice, we also include a mechanism that penalizes nodes if they drop traffic emanating from one of their customers. For a natural objective function, we prove that the price of stability is at most 2. With respect to social welfare, however, the prices of anarchy and stability can both be unbounded, leading us to consider how much we must perturb the system to obtain good stable solutions. We thus focus on the quality of Nash equilibria achievable through centralized incentives; solutions created by an "altruistic entity" (e.g., the government) able to increase individual payouts for successfully routing a particular demand. We show that if every payout is increased by a factor of 2, then there is a Nash equilibrium as good as the original centrally defined social optimum. We also show how to find equilibria efficiently in multicast trees. Finally, we give a characterization of Nash equilibria as flows of utility with certain constraints, which helps to visualize the structure of stable solutions and provides us with useful proof techniques

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs s1t1, s2t2, ..., sktk, the goal is to maximize the number of pairs that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap. Motivated by this, we consider solutions with small constant congestion c > 1; that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems.In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation.We also study limitations on the approximation that can be achieved by a well-linked decomposition. For general graphs we show a lower bound of Ω(log n). For planar graphs we describe instances that suggest a super-constant lower bound.

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].

We study the maximum edge-disjoint paths problem (MEDP). We are given a graph G = (V, E) and a set T = {s/sub 1/t/sup 1/, s/sub 2/t/sup 2/,..., s/sub k/t/sup k/} of pairs of vertices: the objective is to find the maximum number of pairs in T that can be connected via edge-disjoint paths. Our main result is a poly-logarithmic approximation for MEDP on undirected planar graphs if a congestion of 2 is allowed, that is, we allow up to 2 paths to share an edge. Prior to our work, for any constant congestion, only a polynomial-factor approximation was known for planar graphs although much stronger results are known for some special cases such as grids and grid-like graphs. We note that the natural multi-commodity flow relaxation of the problem has an integrality gap of /spl Omega/(/spl radic/|V|) even on planar graphs when no congestion is allowed. Our starting point is the same relaxation and our result implies that the integrality gap shrinks to a poly-logarithmic factor once 2 paths are allowed per edge. Our result also extends to the unsplittable flow problem and the maximum integer multicommodity flow problem. A set X /spl sube/V is well-linked if for each S /spl sub/ V, |/spl delta/(S)| /spl ges/ min{|S /spl cap/ X |, |(V - S) /spl cap/ X|}. The heart of our approach is to show that in any undirected planar graph, given any matching M on a well-linked set X, we can route /spl Omega/(|M|) pairs in M with a congestion of 2. Moreover, all pairs in M can be routed with constant congestion for a sufficiently large constant. This results also yields a different proof of a theorem of Klein, Plotkin, and Rao that shows an O(1) maxflow-mincut gap for uniform multicommodity flow instances in planar graphs. The framework developed in this paper applies to general graphs as well. If a certain graph theoretic conjecture is true, it yields poly-logarithmic integrality gap for MEDP with constant congestion.

We consider the all-or-nothing multicommodity flow problem in general graphs. We are given a capacitated undirected graph G=(V,E,u) and set of k pairs s1t1, s2t2, …, sktk. Each pair has a unit demand. The objective is to find a largest subset S of 1,2,…,k such that for every i in S we can send a flow of one unit between si and ti. Note that this differs from the edge-disjoint path problem (EDP) in that we do not insist on integral flows for the pairs. This problem is NP-hard, and APX-hard, even on trees. For trees, a 2--approximation is known for the cardinality case and a 4--approximation for the weighted case. In this paper we build on a recent result of Racke on low congestion oblivious routing in undirected graphs to obtain a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. The best previous known approximation for all-or-nothing flow problem was O(min(n

We consider the problem of network design in transparent, or clear channel, optical networks associated with wavelength-division multiplexing (WDM). We focus on the class of traffic engineering models known as routing, wavelength, and capacity assignment problems. Here, in contrast to traditional networks, traffic flow paths must also be assigned an end-to-end wavelength. This additional requirement means that there can be an increased cost associated with optimal capacity allocations for such WDM-flows. In general, this can be arbitrarily worse than traditional network designs. We argue that in order to evaluate the benefit of different switch technologies, a good benchmark is to measure the increase in costs purely in terms of link capacity, we call this the cost of transparency. Experimental research shows that this cost is small in multifiber networks with modest switching functionality at the nodes. We present theoretical justification for why this occurs, and prove that in multiwavelength multifiber transparent networks the cost of transparency all but disappears if there is moderate traffic load. Our arguments are based on efficient heuristics that may also be useful for more complex network optimizations. This suggests that the cost savings from using wavelength converters is significant only in young networks with relatively few fibers lit. Such savings may, thus, be small relative to the initial capital expense involved in installing wavelength conversion.

Abstract Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524–539], we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value T from a source s to a destination t . We also impose upper bounds on the amount of capacity we may reserve on the arcs: This alters the nature of the problem. In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum‐cost reservation that is itself an acyclic ( s , t ) flow: We show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc‐disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. © 2003 Wiley Periodicals, Inc.

Damaschke, Müller, and Kratsch [Inform. Process. Lett., 36 (1990), pp. 231-236] gave a polynomial-time algorithm to solve the minimum dominating set problem in convex bipartite graphs $B=(X \cup Y,E)$, that is, where the nodes in Y can be ordered so that each node of X is adjacent to a contiguous sequence of nodes. Gamble et al. [Graphs Combin., 11 (1995), pp. 121-129] gave an extension of their algorithm to weighted dominating sets. We formulate the dominating set problem as that of finding a minimum weight subset of elements of a graphic matroid, which covers each fundamental circuit and fundamental cut with respect to some spanning tree T. When T is a directed path, this simultaneous covering problem coincides with the dominating set problem for the previously studied class of convex bipartite graphs. We describe a polynomial-time algorithm for the more general problem of simultaneous covering in the case when T is an arborescence. We also give NP-completeness results for fairly specialized classes of the simultaneous cover problem. These are based on connections between the domination and induced matching problems.

We consider the problem of client assignment in a distributed system of content servers. We present a system called Webmapper for clustering IP addresses and assigning each cluster to an optimal content server. The system is passive in that the only information it uses comes from monitoring the TCP connections between the clients and the servers. It is also flexible in that it makes no a priori assumptions about network topology and server placement and it can react quickly to changing network conditions. We present experimental results to evaluate the performance of Webmapper.

We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] when route reflection is used. We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists.

We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be "resilient" against one or more arc failures. For a given pair (s,t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an (s,t) flow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to find a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network flow problems, the integral version is NP-hard: we do, however, give a polynomial time $\frac{15}{14}$-approximation algorithm in the case k=1 and show that this bound is best possible unless P = NP.

The border gateway protocol, BGP, is currently the only interdomain routing protocol employed on the Internet. As required of any interdomain protocol, BGP allows policy-based metrics to override distance-based metrics and enables each autonomous system to independently define its routing policies with little or no global coordination. Varadhan et al. (1996) have shown that there are collections of routing policies that together are not safe in the sense that they can cause BGP to diverge. That is, an unsafe collection of routing policies can result in some autonomous systems exchanging BGP routing messages indefinitely, without ever converging to a set of stable routes. In this paper we present sufficient conditions on routing policies that guarantee BGP safety. We use a new formalism, called the simple path vector protocol (SPVP), that is designed to capture the underlying semantics of any path vector protocol such as BGP. We identify a certain circular set of relationships between routing policies at various autonomous systems that we call a dispute cycle. We show that systems with no dispute cycles are guaranteed to be safe. While these include systems whose policies are consistent with shortest paths under some link metric, the class of systems with no dispute cycles is strictly larger.

We study the approximability of two classes of network routing problems.The first class of problems in our study corre spend to classical multicommodity flow problems of the following form: We are given a network G with integer capacities on its edges, together with source-sink pairs (a, ti), 1 5 i 2 k, such that a positive integer demand di and a positive "profit" t'i is associated with eah pair.A feasible solution is a subset S of the (sir ti) pairs such that demands associated with pairs in S can be fully met through a routing which respects all capacity constraints, and the objective is to maximize the total profit associated with the satisfied pairs.We consider two natural variants: unsplittable flow (USF) where each pair must be satisfied by routing all its demand on a single

The richest class of t-perfect graphs known so far consists of the graphs with no so-called odd-K. Clearly, these graphs have the special property that they are hereditary t-perfect in the sense that every subgraph is also t-perfect, but they are not the only ones. In this paper we characterize hereditary t-perfect graphs by showing that any non--t-perfect graph contains a non--t-perfect subdivision of K 4 , called a bad-K 4 . To prove the result we show which "weakly 3-connected" graphs contain no bad-K 4 ; as a side-product of this we get a polynomial time recognition algorithm. It should be noted that our result does not characterize t-perfection, as that is not maintained when taking subgraphs but only when taking induced subgraphs.