Explore the vast range of titles available.

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. [PUBLICATION ABSTRACT]

The authors study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) ... , 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 ... small constant congestion ... 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 they obtained an ... approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper they obtain an ... approximation with congestion 4. To obtain this improvement they develop an alternative decomposition that is specific to planar graphs. (ProQuest: ... denotes formulae/symbols omitted.)

We consider robust (undirected) network design (RND) problems where the set of feasible demands may be given by an arbitrary convex body. This model, introduced by Ben-Ameur and Kerivin [Ben-Ameur W, Kerivin H (2003) New economical virtual private networks. Comm. ACM 46(6):69-73], generalizes the well-studied virtual private network (VPN) problem. Most research in this area has focused on 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 Chekuri [Chekuri C (2007) Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News 38(3):106-128], 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. Gupta pointed out that metric embeddings imply an O (log n )-approximation for the general RND problem, and hence this is tight up to polylogarithmic factors. 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 of 8 in general, and 2 for the case where the tree has unit capacities. As an application of this result, we consider so-called H -tope demand polytopes. These correspond to demands which are routable in some graph H . We show that the corresponding RND problem has an O (1)-approximation if H admits a stochastic constant-distortion embedding into tree metrics.

In multicommodity network flows, a supply–demand graph pair ( G ,  H ) (called a multiflow topology ) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely directed stars and directed triangles. To obtain such characterizations, we introduce a theory of relevant minors . Unlike the undirected setting, for directed graphs the cut-sufficient topologies are not minor-closed. They are however relevant-minor-closed. A single forbidden relevant minor characterizes roundtrip cut-sufficiency, and two suffice for the other classes. We also provide a partial characterization in the case of two independent demands ( 2-matching demands ), showing that one of two relevant minors exists if the weights that break cut-sufficiency have unit demand values. As an application of our results, we show that recognizing cut-sufficiency for directed multiflow topologies is co-NP-hard, even for roundtrip demands. This is in contrast to undirected 2-commodity flows, for which topologies are always cut-sufficient.

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(\\alpha)\\)-approximation whenever (SO) admits an \\(\\alpha\\)-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(\\alpha \\cdot \\min \\{k, \\log^2 (n)\\})\\)-approximation whenever (SO) admits an \\(\\alpha\\)-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 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.

A multiflow in a planar graph is uncrossed if its support paths do not cross. Recently such flows played a role in approximation algorithms for maximum disjoint paths in \"fully-planar\" instances, where the combined supply-demand graph is planar, as well as low-congestion unsplittable flows for fully-planar and single-source instances. We expand on the theory of uncrossed flows to investigate their utility more generally. We ask three key questions. First, are there other interesting planar multiflow instances that admit uncrossed flows? We answer affirmatively, demonstrating a new family of \"pairwise-planar\" instances whose flows can be uncrossed. This family subsumes fully-planar but includes substantially more, such as fully-compliant series-parallel instances, and has instances with clique demand graphs. Second, given a fractional uncrossed flow, can we always round it to a \"good\" integral flow? We again answer positively. For maximization problems (where we maximize the total amount of flow), we obtain integral flows with a constant fraction of the original value. For congestion problems (where we fully route specific given demands), we obtain integral flows with edge congestion 2, or unsplittable flows with an additional additive error. As a consequence we obtain approximation algorithms for maximum disjoint paths and minimum congestion integer multiflow for pairwise-planar instances. Finally, given a planar multiflow instance, can we determine if there exists a congestion 1 uncrossed fractional flow (congestion) or find the highest value uncrossed fractional flow (maximization)? For the congestion model, we show this is NP-hard, but finding uncrossed edge-disjoint paths is polytime solvable if the demands span a bounded number of faces. For the maximization model, we present a strong inapproximability result.