We consider Buy-at-Bulk Network Design with Protection, which is motivated by fault-tolerance in high speed (optical) networks. Given a graph G=(V,E) and a set of demand pairs (s1,t1), …,(sr,tr), the goal is to route a demand of δ(i) for each pair (si,ti) along two internally vertex-disjoint paths (to protect against a vertex failure) so as to minimize the total cost of routing. The cost of the routing is ∑e fe(xe), where xe is the total flow on edge e and fe: ℝ+ → ℝ+ is a sub-additive cost function that models economies of scale for installing capacity on e. We obtain a polylogarithmic approximation for this problem. The algorithm is based on connections and insights from length-constrained network design. Along the way, we obtain a bicriteria approximation algorithm for a 2-vertex connected length-constrained problem, which is of independent interest.

We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N → ℝ_+, r monotone submodular functions f_1,f_2,…,f_r over N and requirements b_1,b_2,…,b_r the goal is to find a minimum cost subset S ⊆ N such that f_i(S) ≥ b_i for 1 ≤ i ≤ r. When r = 1 this is the well-known Submodular Set Cover problem. Previous work [Chekuri et al., 2022] considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each f_i is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Ω(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. When the f_i are weighted coverage functions from a deletion-closed set system we obtain a (1+ε)(e/(e-1))(1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. Second, for covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that f_i(S) ≥ (1-1/e^α-ε)b_i for each i ∈ [r] and 𝔼[c(S)] ≤ (1+ε)α ⋅ OPT. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r = 1. We also demonstrate applications of our results to implicit covering problems such as fair facility location.

We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G = (V, E) and an integer connectivity requirement r(uv) for each u, v ∈ V. The objective is to find a minimum-weight subgraph H ⊆ G such that, for every pair of vertices u, v ∈ V, u and v are r(uv)-edge/vertex-connected. Recent work by [Ce Jin et al., 2024] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). In this work we consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP. - We provide a general framework for solving connectivity problems including SNDP and others in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP we provide an O(tk)-approximation in Õ(k^{1-1/t}n^{1 + 1/t}) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(β t)-approximation where β is the integrality gap of the natural cut-based LP relaxation. These are the first approximation algorithms in the streaming model for VC-SNDP. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^{1/2-1/(2t)}n^{1 + 1/t} + kn) space, improving the O(t log k)-approximation of [Ce Jin et al., 2024] using Õ(kn^{1+1/t}) space; this also extends to element-connectivity SNDP. - We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected spanning subgraph G, and additional weighted links L arrive in the stream; the goal is to store the min-weight set of links such that G ∪ L is (k+1)-vertex-connected. We obtain constant-factor approximations in near-linear space for k = 1, 2. Our result for k = 2 is based on using the SPQR tree, a novel application for this well-known representation of 2-connected graphs.

We consider deletion problems in graphs and supermodular functions where the goal is to reduce density. In Graph Density Deletion (GraphDD), we are given a graph G = (V,E) with non-negative vertex costs and a non-negative parameter ρ ≥ 0 and the goal is to remove a minimum cost subset S of vertices such that the densest subgraph in G-S has density at most ρ. This problem has an underlying matroidal structure and generalizes several classical problems such as vertex cover, feedback vertex set, and pseudoforest deletion set for appropriately chosen ρ ≤ 1 and all of these classical problems admit a 2-approximation. In sharp contrast, we prove that for every fixed integer ρ > 1, GraphDD is hard to approximate to within a logarithmic factor via a reduction from SetCover, thus showing a phase transition phenomenon. Next, we investigate a generalization of GraphDD to monotone supermodular functions, termed Supermodular Density Deletion (SupmodDD). In SupmodDD, we are given a monotone supermodular function f:2^V → ℤ_{≥0} via an evaluation oracle with element costs and a non-negative integer ρ ≥ 0 and the goal is remove a minimum cost subset S ⊆ V such that the densest subset according to f in V-S has density at most ρ. We show that SupmodDD is approximation equivalent to the well-known Submodular Cover problem; this implies a tight logarithmic approximation and hardness for SupmodDD; it also implies a logarithmic approximation for GraphDD, thus matching our inapproximability bound. Motivated by these hardness results, we design bicriteria approximation algorithms for both GraphDD and SupmodDD.

Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms [Schrijver, 2003]. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation [Feige et al., 2002; Cheriyan and Salavatipour, 2007]. Călinescu, Chekuri, and Vondrák [G. Călinescu et al., 2009] viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model [Pananjady et al., 2015; Emek et al., 2019; Bienkowski et al., 2025]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations, we formulate an online model for packing bases of a polymatroid, and describe a randomized algorithm with a polylogarithmic competitive ratio. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [Quanrud, 2024]. We generalize the previously known result for the online disjoint set cover problem [Emek et al., 2019] and also address several other packing problems in a unified fashion. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same poly-logarithmic competitive ratio.

We consider the following question: given a submodular or supermodular set function $f:2^V \to \mathbb{R}$, how should one minimize or maximize its average value $f(S)/|S|$ over non-empty subsets $S\subseteq V$? This problem generalizes several well-known objectives including Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications [39, 31], we formalize two new broad problems: the Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS) which allow negative and non-monotone functions. Using classical results we observe that DSS, SFM, USSS, UDSS, and MNP are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one problem can be repurposed to solve others efficiently. In particular we use the perspective of the minimum norm point in the base polyhedron of a sub/supermodular function which, via Fujishige's results, yields the dense decomposition as a byproduct. Via this perspective we show that a recent converging heuristic for DSS, \textsc{SuperGreedy++} [15, 29], and Wolfe’s minimum norm point algorithm are both universal solvers for all of these problems. On the theoretical front, we explain the observation made in recent work [39, 31] that \textsc{SuperGreedy++} appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including for example that it can act as an effective minimum $st$ cut algorithm. On the empirical front, we explore the utility of several different algorithms including Fujishige-Wolfe min-norm point algorithm for recent problems. We conduct over 400 experiments across seven problem types and large-scale synthetic and real-world datasets (up to $\approx 100$ million edges). Our results reveal that methods historically considered inefficient, such as convex-programming methods, flow-based solvers, and Fujishige-Wolfe’s algorithm, outperform state-of-the-art task-specific baselines by orders of magnitude on concrete problems like HNSN [39]. These findings challenge prevailing assumptions and demonstrate that with the right framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems.

We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is adirected edge-weighted graph G = (V,E ) and a collection of vertex pairs {(si,ti )}i∈[k]. The goal is to find a minimum cost subgraph H of G such that H contains an si -ti path for each i ∈ [k]. DSF is NP-Hard and is known to be hard to approximate to a factor of Ω(2log1-∈ (n )) for any fixed ∈ > 0 [17]. DSF admits approximation ratios of O (K1/2+∈) [10] and O (n2/3+∈) [4].

We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.

We consider two-cost network design models in which edges of the input graph have an associated cost and length. We build upon recent advances in hop-constrained oblivious routing to obtain two sets of results. We address multicommodity buy-at-bulk network design in the nonuniform setting. Existing poly-logarithmic approximations are based on the junction tree approach [CHKS09,KN11]. We obtain a new polylogarithmic approximation via a natural LP relaxation. This establishes an upper bound on its integrality gap and affirmatively answers an open question raised in [CHKS09]. The rounding is based on recent results in hop-constrained oblivious routing [GHZ21], and this technique yields a polylogarithmic approximation in more general settings such as set connectivity. Our algorithm for buy-at-bulk network design is based on an LP-based reduction to hop constrained network design for which we obtain LP-based bicriteria approximation algorithms. We also consider a fault-tolerant version of hop constrained network design where one wants to design a low-cost network to guarantee short paths between a given set of source-sink pairs even when k-1 edges can fail. This model has been considered in network design [GL17,GML18,AJL20] but no approximation algorithms were known. We obtain polylogarithmic bicriteria approximation algorithms for the single-source setting for any fixed k. We build upon the single-source algorithm and the junction-tree approach to obtain an approximation algorithm for the multicommodity setting when at most one edge can fail.

In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k).

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out- degree is proportional to the arboricity α of the graph, in, either, an amortised update time of 𝒪(log2 n log α), or a worst-case update time of 𝒪 (log3 n log α). On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either 𝒪 (log n log α), amortised, or 𝒪(log2 n log α), worst-case, for the problem of maintaining an edge-orientation with at most 𝒪 (α + log n) out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in n and α. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work:

Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem — the All-or-Nothing Multicommodity Flow (ANF) problem — in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities, mandating the need for splittable flows (i.e., flows may not follow a single path). Formally, the input for the ANF problem is an edge-capacitated directed graph where we have a given number of source-destination node-pairs with their respective demands and strictly positive weights. The goal is to route a maximum weight subset of the given pairs (i.e., the weighted throughput), respecting the edge capacities: A commodity is routed if all of its demand is routed from its respective source to destination (this is the all-or-nothing aspect). We present a polynomial-time bi-criteria approximation randomized rounding framework for this NP-hard problem that yields an arbitrarily good approximation on the weighted throughput while violating the edge capacity constraints by at most a sublogarithmic multiplicative factor. We present two non-trivial linear programming relaxations that can be used in the framework; the first uses a novel edge-flow formulation and the second uses a packing formulation. We demonstrate the “equivalence” of these formulations and then highlight the advantages of each of the two approaches. We complement our theoretical results with a proof of concept empirical evaluation, considering a variety of network scenarios.

Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority $k$-Median problem that has recently been studied. The input consists of a set of facilities $\mathcal{F}$ and a set of clients $\mathcal{C}$ that lie in a metric space $(\mathcal{F} \cup \mathcal{C},d)$, and a matroid $\mathcal{M}=(\mathcal{F},\mathcal{I})$ over the facilities. In addition each client $j$ has a specified radius $r_j \ge 0$ and each facility $i \in \mathcal{F}$ has an opening cost $f_i$. The goal is to choose a subset $S \subseteq \mathcal{F}$ of facilities to minimize the $\sum_{i \in \mathcal{F}} f_i + \sum_{j \in \mathcal{C}} d(j,S)$ subject to two constraints: (i) $S$ is an independent set in $\mathcal{M}$ (that is $S \in \mathcal{I}$) and (ii) for each client $j$, its distance to an open facility is at most $r_j$ (that is, $d(j,S) \le r_j$). For this problem we describe the first bicriteria $(c_1,c_2)$ approximations for fixed constants $c_1,c_2$: the radius constraints of the clients are violated by at most a factor of $c_1$ and the objective cost is at most $c_2$ times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting ($r_j := L$ $\forall j \in \mathcal{C}$).

Maximum weight independent set (MWIS) admits a 1/k-approximation in inductively k-independent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)-approximation in k-perfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize k-degenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudo-disks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a non-negative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)-approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or low-adaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively k-independent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primal-dual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudo-disks.

Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Quanrud, and Torres [2] extended the algorithm to general supermodular density problems (of which DSG is a special case) and proved that the resulting algorithm Super-Greedy++ (and hence also Greedy++) converges. In this paper, we revisit the convergence proof and provide a different perspective. This is done via a connection to Fujishige's quadratic program for finding a lexicographically optimal base in a (contra)polymatroid [3], and a noisy version of the Frank-Wolfe method from convex optimisation [4,5]. This gives us a simpler convergence proof, and also shows a stronger property that Super-Greedy++ converges to the optimal dense decomposition vector, answering a question raised in Harb et al. [6]. A second contribution of the paper is to understand Thorup's work on ideal tree packing and greedy tree packing [7,8] via the Frank-Wolfe algorithm applied to find a lexicographically optimum base in the graphic matroid. This yields a simpler and transparent proof. The two results appear disparate but are unified via Fujishige's result and convex optimisation.

Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the flexible graph connectivity model [Adjiashvili, 2013; Adjiashvili et al., 2020; Adjiashvili et al., 2022; Boyd et al., 2023], in which the edge set is partitioned into safe and unsafe edges. Given parameters p,q ≥ 1, the goal is to find a cheap subgraph that remains p-connected even after the failure of q unsafe edges. We also discuss the bulk-robust model [Adjiashvili et al., 2015; Adjiashvili, 2015] and the relative survivable network design model [Dinitz et al., 2022]. While SNDP admits a 2-approximation [K. Jain, 2001], the approximability of problems in these more complex models is much less understood even in special cases. We make two contributions. Our first set of results are in the flexible graph connectivity model. Motivated by a conjecture that a constant factor approximation is feasible when p and q are fixed, we consider two special cases. For the s-t case we obtain an approximation ratio that depends only on p,q whenever p+q > pq/2 which includes (p,2) and (2,q) for all p,q ≥ 1. For the global connectivity case we obtain an O(q) approximation for (2,q), and an O(p) approximation for (p,2) and (p,3) for any p ≥ 1, and for (p,4) when p is even. These are based on an augmentation framework and decomposing the families of cuts that need to be covered into a small number of uncrossable families. Our second result is a poly-logarithmic approximation for a generalization of the bulk-robust model when the "width" of the given instance (the maximum number of edges that can fail in any particular scenario) is fixed. Via this, we derive corresponding approximations for the flexible graph connectivity model and the relative survivable network design model. We utilize a recent framework due to Chen et al. [Chen et al., 2022] that was designed for handling group connectivity.

We study the densest subgraph problem (DSG) and the densest subgraph local decomposition problem (DSG-LD) in undirected graphs. We also consider supermodular generalizations of these problems. For large scale graphs simple iterative algorithms perform much better in practice than theoretically fast algorithms based on network-flow or LP solvers. Boob et al [1] recently gave a fast iterative algorithm called Greedy++ for DSG. It was shown in [2] that it converges to a $(1-\epsilon)$ relative approximation to the optimum density in $O(\frac{1}{\epsilon^2} \frac{\Delta(G)}{\lambda^*})$ iterations where $\Delta(G)$ is the maximum degree and $\lambda^*$ is the optimum density. Danisch et al. [3] gave an iterative algorithm based on the Frank-Wolfe algorithm for DSG-LD that takes $O(\frac{m\Delta(G) }{\epsilon^2})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector $\hat{b}$, where $m$ is number of edges in the graph.In this paper we give a new iterative algorithm for both problems that takes at most $O(\frac{\sqrt{m\Delta(G)}}{\epsilon})$ iterations to converge to an $\epsilon$-additive approximate local decomposition vector; each iteration can be implemented in $O(m)$ time. We describe a fractional peeling technique which has strong empirical performance as well as theoretical guarantees. The algorithm is scalable and simple, and can be applied to graphs with hundreds of millions of edges. We test our algorithm on real and synthetic data sets and show that it provides a significant benefit over previous algorithms. The algorithm and analysis extends to hypergraphs.

The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S ⊆ V of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of DSG via the lens of supermodularity. For this we consider the densest supermodular subset problem (DSS): given a non-negative supermodular function f : 2V → ℝ+, maximize f(S)/|S|. For DSG we describe a simple flow-based algorithm that outputs a (1–∊)-approximation in deterministic Õ(m/∊) time where m is the number of edges. Our algorithm is the first to have a near-linear dependence on m and 1/∊ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed DSG. Greedy peeling algorithms have been very popular for DSG and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for DSS and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al. [12] developed an iterative peeling algorithm for DSG which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a (1–∊)-approximation for any supermodular function f; the key to our proof is to consider an LP formulation that is derived via the Lovász extension of a supermodular function. For DSG the bound on the number of iterations we prove is where Δ is the maximum degree and λ∗ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the 2-approximation for densest-at-least-k subgraph [37] extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of DSS to maximize f(S)/g(|S|) for a concave function g.

In the Priority $k$-Center problem, the input consists of a metric space $(X,d)$, an integer $k$, and for each point $v \in X$ a priority radius $r(v)$. The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X} \frac{1}{r(v)} d(v,S)$. If all $r(v)$'s are uniform, one obtains the $k$-Center problem. Plesník [Plesník, Disc. Appl. Math. 1987] introduced the Priority $k$-Center problem and gave a $2$-approximation algorithm matching the best possible algorithm for $k$-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers. Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].

We consider the fundamental problems of determining the rooted and global edge and vertex connectivities (and computing the corresponding cuts) in directed graphs. For rooted (and hence also global) edge connectivity with small integer capacities we give a new randomized Monte Carlo algorithm that runs in time Õ(n²). For rooted edge connectivity this is the first algorithm to improve on the Ω(n³) time bound in the dense-graph high-connectivity regime. Our result relies on a simple combination of sampling coupled with sparsification that appears new, and could lead to further tradeoffs for directed graph connectivity problems. We extend the edge connectivity ideas to rooted and global vertex connectivity in directed graphs. We obtain a (1+ε)-approximation for rooted vertex connectivity in Õ(nW/ε) time where W is the total vertex weight (assuming integral vertex weights); in particular this yields an Õ(n²/ε) time randomized algorithm for unweighted graphs. This translates to a Õ(KnW) time exact algorithm where K is the rooted connectivity. We build on this to obtain similar bounds for global vertex connectivity. Our results complement the known results for these problems in the low connectivity regime due to work of Gabow [Harold N. Gabow, 1995] for edge connectivity from 1991, and the very recent work of Nanongkai et al. [Nanongkai et al., 2019] and Forster et al. [Sebastian Forster et al., 2020] for vertex connectivity.

Li and Panigrahi [Jason Li and Debmalya Panigrahi, 2020], in recent work, obtained the first deterministic algorithm for the global minimum cut of a weighted undirected graph that runs in time o(mn). They introduced an elegant and powerful technique to find isolating cuts for a terminal set in a graph via a small number of s-t minimum cut computations. In this paper we generalize their isolating cut approach to the abstract setting of symmetric bisubmodular functions (which also capture symmetric submodular functions). Our generalization to bisubmodularity is motivated by applications to element connectivity and vertex connectivity. Utilizing the general framework and other ideas we obtain significantly faster randomized algorithms for computing global (and subset) connectivity in a number of settings including hypergraphs, element connectivity and vertex connectivity in graphs, and for symmetric submodular functions.

We consider the complexity of minmax partitioning of graphs, hypergraphs and (symmetric) submodular functions. Our main result is an algorithm for the problem of partitioning the ground set of a given symmetric submodular function f : 2V → ℝ into k non-empty parts V1, V2, …, Vk to minimize . Our algorithm runs in time, where n = |V| and T is the time to evaluate f on a given set; hence. this yields a polynomial time algorithm for any fixed k in the evaluation oracle model. As an immediate corollary, for any fixed k, there is a polynomial-time algorithm for the problem of partitioning the vertex set of a given hypergraph H = (V, E) into k non-empty parts to minimize the maximum capacity of the parts. The complexity of this problem. termed Minmax-Hypergraph-k-Part, was raised by Lawler in 1973 [16]. In contrast to our positive result, the reduction in [6] implies that when k is part of the input, Minmax-Hypergraph-k-Part is hard to approximate to within an almost polynomial factor under the Exponential Time Hypothesis (ETH).

We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.

We consider the Hypergraph- k-Cut problem. The input consists of a hypergraph G = (V, E) with nonnegative hyperedge-costs c:E→ \mathbbR+ and a positive integer k. The objective is to find a least-cost subset F ⊆ E such that the number of connected components in G-F is at least k. An alternative formulation of the objective is to find a partition of V into k non-empty sets V1, V2, ..., Vk so as to minimize the cost of the hyperedges that cross the partition. Graph- k-Cut, the special case of Hypergraph- k-Cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph- k-Cut when k is fixed, starting with the work of Goldschmidt and Hochbaum (1988) [1], [2]. In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph- k-Cut was developed [3] via a subtle generalization of Karger's random contraction approach for graphs. In this work, we develop the first deterministic polynomial time algorithm for Hypergraph- k-Cut for all fixed k. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in nO(k2) time while the second one runs in nO(k)time. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum k-partition by solving minimum ( S, T) -terminal cuts. Our techniques give new insights even for Graph- k-Cut.

We derive fast approximation schemes for LP relaxations of several well-studied geometric optimization problems that include packing, covering, and mixed packing and covering constraints. Previous work in computational geometry concentrated mainly on the rounding stage to prove approximation bounds, assuming that the underlying LPs can be solved efficiently. This work demonstrates that many of those results can be made to run in nearly linear time. In contrast to prior work on this topic our algorithms handle weights and capacities, side constraints, and also apply to mixed packing and covering problems, in a unified fashion. Our framework relies crucially on the properties of a randomized MWU algorithm of [41]; we demonstrate that it is well-suited for range spaces that admit efficient approximate dynamic data structures for emptiness oracles. Our framework cleanly separates the MWU algorithm for solving the LP from the key geometric data structure primitives, and this enables us to handle side constraints in a simple way. Combined with rounding algorithms that can also be implemented efficiently, we obtain the first near-linear constant factor approximation algorithms for several problems.

Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46--76] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm [D. R. Karger, Random Sampling in Graph Optimization Problems, Ph.D. thesis, Stanford University, Stanford, CA, 1995, D. R. Karger and C. Stein, J. ACM, 43 (1996), pp. 601--640]. Thorup developed a fast deterministic algorithm for the minimum $k$-cut problem via greedy recursive tree packings [M. Thorup, Minimum $k$-way cuts via deterministic greedy tree packing, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 159--166]. In this paper we revisit properties of an LP relaxation for cͅut proposed by Naor and Rabani [ Tree packing and approximating $k$-cuts, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 103, SIAM, Philadelphia, 2001, pp. 26--27], and analyzed in [C. Chekuri, S. Guha, and J. Naor, SIAM J. Discrete Math., 20 (2006), pp. 261--271]. We show that the dual of the LP yields a tree packing that, when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Karger's analysis for mincut to the $k$-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorup's algorithm by a factor of $n$. We also improve the bound on the number of $\alpha$-approximate $k$-cuts. Second, we give a simple proof that the integrality gap of the LP is $2(1-1/n)$. Third, we show that an optimum solution to the LP relaxation, for all values of $k$, is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of Barahona [ Oper. Res. Lett., 26 (2000), pp. 99--105] and Ravi and Sinha [ European J. Oper. Res., 186 (2008), pp. 77--90]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP.

Balkanski and Singer [4] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Subsequent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal (1 – 1/e – ∊)-approximation in O(log n/∊2) rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints. Formally our problem is to maximize F(x) over x ∊ [0, 1]n subject to where F is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal (1 – 1/e – ∊)-approximation in O(log2 m log n/∊4) rounds where n is the cardinality of the ground set and m is the number of packing constraints. For many constraints of interest, the resulting fractional solution can be rounded via known randomized rounding schemes that are oblivious to the specific submodular function. We thus derive randomized algorithms with poly-logarithmic adaptivity for a number of constraints including partition and laminar matroids, matchings, knapsack constraints, and their intersections. Our algorithm takes a continuous view point and combines several ideas ranging from the continuous greedy algorithm of [38, 13], its adaptation to the MWU framework for packing constraints [20], and parallel algorithms for packing LPs [31, 41]. For the basic setting of cardinality constraints, this viewpoint gives rise to an alternative, simple to understand algorithm that matches recent results [6, 21]. Our algorithm to solve the multilinear relaxation is deterministic if it is given access to a value oracle for the multilinear extension and its gradient; this is possible in some interesting cases such as the coverage function of an explicitly given set system.

We consider approximation algorithms for covering integer programs of the form min 〈c, x〉 over x ∊ ℤ≥0n s.t. Ax ≥ b and x ≤ d; where A ∊ ℝ≥0m×n, b ∊ ℝ≥0m, and c, d ∊ ℝ≥0n all have nonnegative entries. We refer to this problem as CIP, and the special case without the multiplicity constraints x < d as CIP∞. These problems generalize the well-studied Set Cover problem. We make two algorithmic contributions. First, we show that a simple algorithm based on randomized rounding with alteration improves or matches the best known approximation algorithms for CIP and CIP∞ in a wide range of parameter settings, and these bounds are essentially optimal. As a byproduct of the simplicity of the alteration algorithm and analysis, we can derandomize the algorithm without any loss in the approximation guarantee or efficiency. Previous work by Chen, Harris and Srinivasan [13] which obtained near-tight bounds is based on a resampling-based randomized algorithm whose analysis is complex. Non-trivial approximation algorithms for CIP are based on solving the natural LP relaxation strengthened with knapsack cover (KC) inequalities [5, 26, 13]. Our second contribution is a fast (essentially near-linear time) approximation scheme for solving the strengthened LP with a factor of n speed up over the previous best running time [5]. To achieve this fast algorithm we combine recent work on accelerating the multiplicative weight update framework with a partially dynamic approach to the knapsack covering problem. Together, our contributions lead to near-optimal (deterministic) approximation bounds with near-linear running times for CIP and CIP∞.

We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized (1 / 2 − є)-approximation in O( log2(n) / 2 ) rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondrák to obtain a fractional solution that yields a near-optimal randomized ( 1 − 1/e − є )-approximation in O( log2(n) / є3 ) rounds of adaptivity. For non-negative functions we obtain a ( 3−2√2 − є )-approximation and a fractional solution that yields a ( 1 / e − є)-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.

We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [ICS, 2010] and Awasthi, Blum and Sheffet [Inf. Proc. Lett., 2012]. A clustering instance $I$ is said to be $α$-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of $α$ and the perturbed distances satisfy the metric property --- this is the metric perturbation resilience property introduced in Angelidakis et. al. [STOC, 2010] and a weaker requirement than prior models. We make two high-level contributions. 1) We show that the natural LP relaxation of $k$-center and asymmetric $k$-center is integral for $2$-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results that are based on combinatorial algorithms designed for the perturbation model. 2) We define a simple new model of perturbation resilience for clustering with \emph{outliers}. Using this model we show that the unified MST and dynamic programming based algorithm proposed by Angelidakis et. al. [STOC, 2010] exactly solves the clustering with outliers problem for several common center based objectives (like $k$-center, $k$-means, $k$-median) when the instances is $2$-perturbation resilient. We further show that a natural LP relxation is integral for $2$-perturbation resilient instances of \kcenter with outliers.

We describe and analyze a simple randomized multiplicative weight update (MWU) based algorithm for approximately solving positive linear programming problems, in particular, mixed packing and covering LPs. Given m explicit linear packing and covering constraints over n variables specified by N nonzero entries, Young [36] gave a deterministic algorithm returning an (1 + ε)-approximate feasible solution (if a feasible solution exists) in Õ(N/ε2) time. We show that a simple randomized implementation matches this bound, and that randomization can be further exploited to improve the running time to Õ(N/ε + m/ε2 + n/ε3) (both with high probability). For instances that are not very sparse (with at least ῶ(1/ε) nonzeroes per column on average), this improves the running time of Õ(N/ε2). The randomized algorithm also gives improved running times for some implicitly defined problems that arise in combinatorial and geometric optimization.

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph $H=(V,E)$ with $n = |V|$, $m = |E|$, and $p = \sum_{e \in E} |e|$ the fastest known algorithm to compute a global minimum cut in $H$ runs in $O(np)$ time for the uncapacitated case, and in $O(np + n^2 \log n)$ time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph $H$ and an integer $k$ we describe an algorithm that runs in $O(p)$ time to find a (trimmed) subhypergraph $H'$ with sum of degrees $O(kn)$ that preserves all edge-connectivities up to $k$ (a $k$-sparse certificate). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an $O(p + \lambda n^2)$ time algorithm for computing a global minimum cut of $H$ where $\lambda$ is the minimum cut value. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in $O(np + n^2 \log n)$ time and $O(p)$ space matching the asymptotic time to find a single minimum cut. We obtain a $(2+\epsilon)$-approximation to the global minimum cut of a capacitated hypergraph in $O(\frac{1}{\epsilon} (p \log n + n \log^2 n))$ time and for uncapacitated hypergraphs in $O(p/\epsilon)$ time. We achieve this by generalizing Matula's algorithm for graphs to hypergraphs. We describe an algorithm to compute approximate strengths of all the edges of a hypergraph in $O(p \log^2 n \log p)$ time. This gives a near linear time algorithm for finding a $(1+\epsilon)$-cut sparsifier based on the work of Kogan and Krauthgamer. As a byproduct we obtain faster algorithms for various cut and flow problems in hypergraphs of small rank. Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several orderings for hypergraphs, and these yield different insights.

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [ J. Algorithms, 10 (1989), pp. 568--576; J. Combin. Theory, Ser. B, 57 (1993), pp. 196--206], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an $O(1)$-approximation is not ruled out, only an $O(\sqrt{n})$-approximation [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317--322] is known even in bounded-degree graphs. In this paper we give a polynomial-time algorithm which, given a bounded-degree graph of Euler genus $g$, computes a drawing in a surface of Euler genus $g^{O(1)} \cdot \log^{O(1)} n$. Combined with the upper bound from [J. Chen, S. P. Kanchi, and A. Kanevsky, Inform. Process. Lett., 61 (1997), pp. 317--322], our result also implies a $O(n^{1/2 - \alpha})$-approximation for some constant $\alpha>0$. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a uniform fashion, algorithms with approximation ratios of the form $\mathsf{OPT}^{O(1)} \cdot \log^{O(1)} n$ for several related problems on bounded-degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion. Our algorithm and proof of correctness for the crossing number problem are simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [ Proceedings of the ACM Symposium on Theory of Computing, 2011, pp. 303--312], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of the form $\operatorname{poly}(\mathsf{OPT},\log n)$. We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph $G=(V,E)$ and a collection of $k$ source-destination pairs $\mathcal{M} = \{s_1t_1, \dots, s_kt_k\}$. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair $s_it_i$ is routed in the symmetric setting if there is a directed path connecting $s_i$ to $t_i$ and a directed path connecting $t_i$ to $s_i$. In this paper we obtain a randomized polylogarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth $h$ contains a relaxed cylindrical grid (which can serve as a constant congestion crossbar in the context of a routing algorithm) of size $\Omega(h/\mathrm{polylog}(h))$.

We give a nearly linear-time randomized approximation scheme for the Held-Karp bound [22] for Metric-TSP. Formally, given an undirected edge-weighted graph G = (V, ε) on m edges and ε > 0, the algorithm outputs in O(m log4n/ε2) time, with high probability, a (1 + ε)-approximation to the Held-Karp bound on the Metric-TSP instance induced by the shortest path metric on G. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the O(m2log2(m)/ε2) running time achieved previously by Garg and Khandekar.

In the minimum Multicut problem, the input is an edge- weighted supply graph G = (V, E) and a demand graph H = (V, F). Either G and H are directed (Dir-MülC) or both are undirected (Undir-MülC). The goal is to remove a minimum weight set of supply edges E’ ⊆ E such that in G — E’ there is no path from s to t for any demand edge (s,t) ∊ F. Undir-MülC admits O(log k)-approximation where k is the number of edges in H while the best known approximation for Dir-MülC is min{k, Õ(|V|11/23)}. These approximations are obtained by proving corresponding results on the multicommodity flow-cut gap. In this paper we consider the role that the structure of the demand graph plays in determining the approximability of Multicut. We obtain several new positive and negative results. In undirected graphs our main result is a 2- approximation in nO(t) time when the demand graph excludes an induced matching of size t. This gives a constant factor approximation for a specific demand graph that motivated this work, and is based on a reduction to uniform metric labeling and not via the flow-cut gap. In contrast to the positive result for undirected graphs, we prove that in directed graphs such approximation algorithms can not exist. We prove that, assuming the Unique Games Conjecture (UGC), that for a large class of fixed demand graphs Dir-MülC cannot be approximated to a factor better than the worst- case flow-cut gap. As a consequence we prove that for any fixed k, assuming UGC, Dir-MülC with k demand pairs is hard to approximate to within a factor better than k. On the positive side, we obtain a k approximation when the demand graph excludes certain graphs as an induced subgraph. This generalizes the known 2 approximation for directed Multiway Cut to a larger class of demand graphs.

We consider several implicit fractional packing problems and obtain faster implementations of approximation schemes based on multiplicative-weight updates. This leads to new algorithms with near-linear running times for some fundamental problems in combinatorial optimization. We highlight two concrete applications. The first is to find the maximum fractional packing of spanning trees in a capacitated graph; we obtain a (1 - ∊)-approximation in Õ(m/∊2) time, where m is the number of edges in the graph. Second, we consider the LP relaxation of the weighted unsplittable flow problem on a path and obtain a (1 - ∊)-approximation in O(n/∊2) time, where n is the number of demands.

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph $H=(V,E)$ with $n = |V|$, $m = |E|$, and $p = \sum_{e \in E} |e|$ the fastest known algorithm to compute a global minimum cut in $H$ runs in $O(np)$ time for the uncapacitated case, and in $O(np + n^2 \log n)$ time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph $H$ and an integer $k$ we describe an algorithm that runs in $O(p)$ time to find a (trimmed) subhypergraph $H'$ with sum of degrees $O(kn)$ that preserves all edge-connectivities up to $k$ (a $k$-sparse certificate). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an $O(p + \lambda n^2)$ time algorithm for computing a global minimum cut of $H$ where $\lambda$ is the minimum cut value. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in $O(np + n^2 \log n)$ time and $O(p)$ space matching the asymptotic time to find a single minimum cut. We obtain a $(2+\epsilon)$-approximation to the global minimum cut of a capacitated hypergraph in $O(\frac{1}{\epsilon} (p \log n + n \log^2 n))$ time and for uncapacitated hypergraphs in $O(p/\epsilon)$ time. We achieve this by generalizing Matula's algorithm for graphs to hypergraphs. We describe an algorithm to compute approximate strengths of all the edges of a hypergraph in $O(p \log^2 n \log p)$ time. This gives a near linear time algorithm for finding a $(1+\epsilon)$-cut sparsifier based on the work of Kogan and Krauthgamer. As a byproduct we obtain faster algorithms for various cut and flow problems in hypergraphs of small rank. Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several orderings for hypergraphs, and these yield different insights.

In [Directed tree-width, J. Combin. Theory Ser. B 82 (2001), 138-154] we introduced the notion of tree-width of directed graphs and presented a conjecture, formulated during discussions with Noga Alon and Bruce Reed, stating that a digraph of huge tree-width has a large "cylindrical grid" minor. Here we prove the conjecture for planar digraphs, but many steps of the proof work in general. This is an unedited and unpolished manuscript from October 2001. Since many people asked for copies we are making it available in the hope that it may be useful. The conjecture was proved by Kawarabayashi and Kreutzer in arXiv:1411.5681.

The minimum $s$-$t$ cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multiway relationships and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a “cut hyperedge” is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph $s$-$t$ cut problem can be reduced to a tractable graph $s$-$t$ cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. Finally, we outline several open questions on general hypergraph cut problems.

We consider subset feedback edge and vertex set problems in undirected graphs. The input to these problems is an undirected graph G = (V, E) and a set S = {s1, s2, …, sk} ⊂ V of k terminals. A cycle in G is interesting if it contains a terminal. In the Subset Feedback Edge Set problem (Subset-FES) the input graph is edge-weighted and the goal is to remove a minimum weight set of edges such that no interesting cycle remains. In the Subset Feedback Vertex Set problem (Subset-FVS) the input graph is node-weighted and the goal is to remove a minimum weight set of nodes such that no interesting cycle remains. A 2-approximation is known for Subset-FES [12] and a 8-approximation is known for Subset-FVS [13]. The algorithm and analysis for Subset-FVS is complicated. One reason for the difficulty in addressing feedback set problems in undirected graphs has been the lack of LP relaxations with constant factor integrality gaps; the natural LP has an integrality gap of ⊝(log n). In this paper, we introduce new LP relaxations for Subset-FES and Subset-FVS and show that their integrality gap is at most 13. Our LP formulation and rounding are simple although the analysis is non-obvious.

We present an approximation algorithm for the maximum weight matroid intersection problem in the independence oracle model. Given two matroids defined over a common ground set N of n elements, let k be the rank of the matroid intersection and let Q denote the cost of an independence query for either matroid. An exact algorithm for finding a maximum cardinality independent set (the unweighted case), due to Cunningham, runs in O(nk1.5Q) time. For the weighted case, algorithms due to Frank and Brezovec et al. run in O(nk2Q) time. There are also scaling based algorithms that run in time, where W is the maximum weight (assuming all weights are integers), and ellipsoid-style algorithms that run in O((n2 log(n)Q + n3 polylog(n))log(nW)) time. Recently, Huang, Kakimura, and Kamiyama described an algorithm that gives a (1 – ∊)-approximation for the weighted matroid intersection problem in O(nk1.5 log(k)Q/∊) time. We observe that a (1 – ∊)-approximation for the maximum cardinality case can be obtained in O(nkQ/∊) time by terminating Cunningham's algorithm early. Our main contribution is a (1 – ∊) approximation algorithm for the weighted matroid intersection problem with running time O(nk log2 (1/∊)Q/∊2).

One of the key results in Robertson and Seymour’s seminal work on graph minors is the grid-minor theorem (also called the excluded grid theorem ). The theorem states that for every grid H , every graph whose treewidth is large enough relative to | V ( H )| contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f ( k ) denote the largest value such that every graph of treewidth k contains a grid minor of size ( f ( k ) × f ( k )). The best previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that f ( k )=Ω(√log k /log log k ). In contrast, the best known upper bound implies that f ( k ) = O (√ k /log k ). In this article, we obtain the first polynomial relationship between treewidth and grid minor size by showing that f ( k ) = Ω( k δ ) for some fixed constant δ > 0, and describe a randomized algorithm, whose running time is polynomial in | V ( G )| and k , that with high probability finds a model of such a grid minor in G .

We develop a continuous-time framework based on multiplicative weight updates to approximately solve continuous optimization problems. The framework allows for a simple and modular analysis for a variety of problems involving convex constraints and concave or submodular objective functions. The continuous-time framework avoids the cumbersome technical details that are typically necessary in actual algorithms. We also show that the continuous-time algorithms can be converted into implementable algorithms via a straightforward discretization process. Using our framework and additional ideas we obtain significantly faster algorithms compared to previously known algorithms to maximize the multilinear relaxation of a monotone or non-monotone submodular set function subject to linear packing constraints.

We consider the single-unicast communication problem in a network with a delay constraint. For this setting, it has recently been shown that network coding offers an advantage over routing. We show that the existing upper bound in the literature on the capacity offered by network coding can be a factor of Θ(D) larger than the true capacity where D is the delay bound. In this work, we tighten this gap significantly to 8 log(D + 1) by proving a new upper bound. The key insight is a connection to a new traffic model that we call triangle-cast (or degraded multiple-unicast), for which we obtain a logarithmic flow-cut gap by suitably adapting the techniques from the approximation algorithms literature.

We consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [Math. Oper. Res., 7 (1982), pp. 334--347] and Hassin [On Network Flows, Ph.D. dissertation, Yale University, New Haven, CT, 1978] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [Ann. Discrete Math., 1 (1977), pp. 185--204]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far we are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks. We also consider the notion of undirected polymatroidal networks and observe that they provide a natural way to generalize flows and cuts in edge and node capacitated undirected networks. We establish flow-cut gap results in several scenarios that have been previously considered in the standard network flow models where capacities are on the edges or nodes. Our results are based on analyzing the dual of the flow relaxations via continuous extensions of submodular functions, in particular, the Lovász extension. For directed graphs we rely on a simple yet useful reduction from polymatroidal networks to standard networks. For undirected graphs we rely on the interplay between the Lovász extension of a submodular function and line embeddings with low average distortion introduced by Matousek and Rabinovich [Israel J. Math., 123 (2001), pp. 285--301]; this connection is inspired by, and generalizes, the work of Feige, Hajiaghayi, and Lee on node-capacitated multicommodity flows and cuts. Our results have found applications in wireless network information flow [S. Kannan and P. Viswanath, IEEE Trans. Inform. Theory, 60 (2014), pp. 6303--6328] and we anticipate others in the future.

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains H as a minor. This theorem has found many applications in graph theory and algorithms. Let f(k) denote the largest value, such that every graph of treewidth k contains a grid minor of size f(k) × f(k). The best current quantitative bound, due to recent work of Kawarabayashi and Kobayashi [15], and Leaf and Seymour [18], shows that f(k) = Ω(√logk/loglogk). In contrast, the best known upper bound implies that f(k) = O(√k/logk) [22]. In this paper we obtain the first polynomial relationship between treewidth and grid-minor size by showing that f(k) = Ω(kδ) for some fixed constant δ > 0, and describe an algorithm, whose running time is polynomial in |V (G)| and k, that finds a model of such a grid-minor in G.

We consider the problem of maximizing a nonnegative submodular set function $f:2^N \rightarrow {\mathbb R}_+$ over a ground set $N$ subject to a variety of packing-type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular, when $f$ may be a nonmonotone function. Our algorithms are based on (approximately) maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully, it has been limited in some important ways. We overcome these limitations as follows. First, we give constant factor approximation algorithms to maximize $F$ over a downward-closed polytope $P$ described by an efficient separation oracle. Previously this was known only for monotone functions. For nonmonotone functions, a constant factor was known only when the polytope was either the intersection of a fixed number of knapsack constraints or a matroid polytope. Second, we show that contention resolution schemes are an effective way to round a fractional solution, even when $f$ is nonmonotone. In particular, contention resolution schemes for different polytopes can be combined to handle the intersection of different constraints. Via linear programming duality we show that a contention resolution scheme for a constraint is related to the correlation gap of weighted rank functions of the constraint. This leads to an optimal contention resolution scheme for the matroid polytope. Our results provide a broadly applicable framework for maximizing linear and submodular functions subject to independence constraints. We give several illustrative examples. Contention resolution schemes may find other applications.

Given an undirected graph $G=(V,E)$ and a subset of vertices called terminals $T \subseteq V$, the element-connectivity $\elconn_G(u,v)$ of two terminals $u,v \in T$ is the maximum number of $u$-$v$ paths that are pairwise element-disjoint, that is, disjoint in both edges and nonterminals $V \setminus T$. (Element-connectivity was first (implicitly) defined by Frank, Ibaraki, and Nagamochi in [J. Graph Theory, 17 (1993), pp. 275--281].) (Element-disjoint paths need not be disjoint in terminals.) Hind and Oellermann [\em Congr. Numer.}, 113 (1996), pp. 179--204] gave a graph reduction step that preserves the global element-connectivity of the terminals. We show that one can also apply such a reduction step while preserving local connectivity, that is, all the pairwise element-connectivities of the terminals. We illustrate the usefulness of this more general reduction step by giving applications to packing element-disjoint Steiner trees and forests: Given a graph $G$ and disjoint terminal sets $T_1, T_2, \ldots, T_h$, we seek a maximum number of element-disjoint Steiner forests where each forest connects each $T_i$. We prove that if each $T_i$ is $k$-element-connected, then there exist $\Omega(\frac{k}{\log |T| \log h})$ element-disjoint Steiner forests, where $T = \bigcup_i T_i$. If $G$ is planar (or has fixed genus), we show that there exist $\Omega(k)$ Steiner forests. Our proofs are constructive, giving poly-time algorithms to find these forests; these are the first nontrivial algorithms for packing element-disjoint Steiner forests.

The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology. Computing it has been shown to be NP-hard by Thomassen [23], [24], and it is known to be fixed-parameter tractable. However, the approximability of the Euler genus is wide open. While the existence of an O(1)-approximation is not ruled out, only an O(√n)-approximation [3] is known even in bounded degree graphs. In this paper we give a polynomialtime algorithm which on input a bounded-degree graph of Euler genus g, computes a drawing into a surface of Euler genus gO(1)· logO(1)n. Combined with the upper bound from [3], our result also implies a O(n1/2-α)-approximation, for some constant α > 0. Using our algorithm for approximating the Euler genus as a subroutine, we obtain, in a unified fashion, algorithms with approximation ratios of the form OPTO(1)· logO(1)n for several related problems on bounded degree graphs. These include the problems of orientable genus, crossing number, and planar edge and vertex deletion problems. Our algorithm and proof of correctness for the crossing number problem is simpler compared to the long and difficult proof in the recent breakthrough by Chuzhoy [5], while essentially obtaining a qualitatively similar result. For planar edge and vertex deletion problems our results are the first to obtain a bound of form poly(OPT, log n). We also highlight some further applications of our results in the design of algorithms for graphs with small genus. Many such algorithms require that a drawing of the graph is given as part of the input. Our results imply that in several interesting cases, we can implement such algorithms even when the drawing is unknown.

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 consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s1, t1), …, (sk, tk)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first poly-logarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph G into node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs h, and the desired lower bound r on the treewidth of each subgraph. The theorems assert that, given a graph G with treewidth k, a decomposition with parameters h,r is feasible whenever hr2 ≤ k/polylog(k), or h3r ≤ k/polylog(k) holds. We then show a framework for using these theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster algorithms for some fixed-parameter tractable problems.

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 consider multicommodity flow and cut problems in polymatroidal networks where there are submodular capacity constraints on the edges incident to a node. Polymatroidal networks were introduced by Lawler and Martel [20] and Hassin [15] in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles [10]; the well-known maxflow-mincut theorem holds in this more general setting. Polymatroidal networks for the multicommodity case have not, as far as the authors are aware, been previously explored. Our work is primarily motivated by applications to information flow in wireless networks.

We consider the set multicover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F , we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by (contained in) at least d(p) sets. Here, d(p) is an integer demand (requirement) for p. When the demands d(p) = 1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this article, we show that similar improvements can be obtained for the multicover problem as well. In particular, we obtain an O (log opt) approximation for set systems of bounded VC-dimension, and an O (1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.

In this article, we consider the orienteering problem in undirected and directed graphs and obtain improved approximation algorithms. The point to point-orienteering problem is the following: Given an edge-weighted graph G =( V, E ) (directed or undirected), two nodes s, t ∈ V and a time limit B , find an s - t walk in G of total length at most B that maximizes the number of distinct nodes visited by the walk. This problem is closely related to tour problems such as TSP as well as network design problems such as k -MST. Orienteering with time-windows is the more general problem in which each node v has a specified time-window [ R ( v ), D ( v )] and a node v is counted as visited by the walk only if v is visited during its time-window. We design new and improved algorithms for the orienteering problem and orienteering with time-windows. Our main results are the following: — A (2+ϵ) approximation for orienteering in undirected graphs, improving upon the 3-approximation of Bansal et al. [2004]. — An O (log 2 OPT) approximation for orienteering in directed graphs, where OPT ≤ n is the number of vertices visited by an optimal solution. Previously, only a quasipolynomial-time algorithm due to Chekuri and Pál [2005] achieved a polylogarithmic approximation (a ratio of O (log OPT)). — Given an α approximation for orienteering, we show an O (α ċ max{log OPT, log l max / l min }) approximation for orienteering with time-windows, where l max and l min are the lengths of the longest and shortest time-windows respectively.

We study algorithms for the SUBMODULAR Multiway PARTITION problem (SUB-MP). An instance of SUB-MP consists of a finite ground set V, a subset S = {s1, S2, ..., sk} ⊆ V of k elements called terminals, and a non-negative submodular set function f : 2V→ ℝ+on V provided as a value oracle. The goal is to partition V into k sets A1,...,Akto minimize Σi=1kf(Ai) such that for 1 ≤ i ≤ k, si∈ Ai. SUB-MP generalizes some well-known problems such as the MULTIWAY CUT problem in graphs and hypergraphs, and the NODE-WEIGHED MULTIWAY Cut problem in graphs. SUB-MP for arbitrary sub- modular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki [29]. Previous algorithms were based on greedy splitting and divide and conquer strategies. In recent work [5] we proposed a convex-programming relaxation for SUB-MP based on the Lovasz-extension of a submodular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary submodular functions via this relaxation. (1) A 2-approximation for SUB-MP. This improves the (k - 1)-approximation from [29]. (2) A (1.5 - 1/k)-approximation for SUB-MP when f is symmetric. This improves the 2(1 - 1/k)-approximation from [23], [29].

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an α-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + ε)-approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant ε > 0. PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approximability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution x in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point x can be rounded to a random solution R such that E[1R] = (1 − δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on S and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].

We consider the problem of maximizing a non-negative submodular set function f:2N -> RR+ over a ground set N subject to a variety of packing type constraints including (multiple) matroid constraints, knapsack constraints, and their intersections. In this paper we develop a general framework that allows us to derive a number of new results, in particular when f may be a non-monotone function. Our algorithms are based on (approximately) solving the multilinear extension F of f [5] over a polytope P that represents the constraints, and then effectively rounding the fractional solution. Although this approach has been used quite successfully in some settings [6, 22, 24, 13, 3], it has been limited in some important ways. We overcome these limitations as follows.

Let $f:2^X \rightarrow \cal R_+$ be a monotone submodular set function, and let $(X,\cal I)$ be a matroid. We consider the problem ${\rm max}_{S \in \cal I} f(S)$. It is known that the greedy algorithm yields a $1/2$-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73–87] for this problem. For certain special cases, e.g., ${\rm max}_{|S| \leq k} f(S)$, the greedy algorithm yields a $(1-1/e)$-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning $f(S)$ for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177–188] and for explicitly posed instances assuming $P \neq NP$ [U. Feige, J. ACM, 45 (1998), pp. 634–652]. In this paper, we provide a randomized $(1-1/e)$-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307–328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the $38$th ACM Symposium on Theory of Computing, 2008, pp. 67–74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires $|X|$ to be exponential in the original problem size, we are able to achieve a $(1-1/e-o(1))$-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.

In the generalized connectivity problem, we are given an edge-weighted graph G = ( V , E ) and a collection D = {( S 1 , T 1 ), …, ( S k , T k )} of distinct demands each demand ( S i , T i ) is a pair of disjoint vertex subsets. We say that a subgraph F of G connects a demand ( S i , T i ) when it contains a path with one endpoint in S i and the other in T i . The goal is to identify a minimum weight subgraph that connects all demands in D . Alon et al. (SODA '04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as Steiner forest, facility location with nonmetric costs, tree multicast, and group Steiner tree. Obtaining a nontrivial approximation ratio for generalized connectivity was left as an open problem. We describe the first poly-logarithmic approximation algorithm for generalized connectivity that has a performance guarantee of O (log 2 n log 2 k ). Here, n is the number of vertices in G and k is the number of demands. We also prove that the cut-covering relaxation of this problem has an O (log 3 n log 2 k ) integrality gap. Building upon the results for generalized connectivity, we obtain improved approximation algorithms for two problems that contain generalized connectivity as a special case. For the directed Steiner network problem, we obtain an O ( k 1/2 + ϵ ) approximation which improves on the currently best performance guarantee of Õ ( k 2/3 ) due to Charikar et al. (SODA '98). For the set connector problem, recently introduced by Fukunaga and Nagamochi (IPCO '07), we present a poly-logarithmic approximation; this result improves on the previously known ratio which can be Ω( n ) in the worst case.

We consider the problem of randomly rounding a fractional solution x in an integer polytope P ⊆ [0,1]nto a vertex X of P, so that E[X] = x. Our goal is to achieve concentration properties for linear and submodular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two poly topes: the assignment poly tope (that is, bipartite matchings and 6-matchings) [32], [19], [23], and more recently for the spanning tree poly tope [2]. These schemes have led to a number of new algorithmic results. In this paper we describe a new swap rounding technique which can be applied in a variety of settings including matroids and matroid intersection, while providing Chernoff-type concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use a martingale argument to obtain an exponential tail estimate for monotone submodular functions. The rounding scheme explicitly exploits exchange properties of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications [19], [23], [7], [22], [2] as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper.

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

Buy-at-bulk network design problems arise in settings where the costs for purchasing or installing equipment exhibit economies of scale. The objective is to build a network of cheapest cost to support a given multicommodity flow demand between node pairs. We present approximation algorithms for buy-at-bulk network design problems with costs on both edges and nodes of an undirected graph. Our main result is the first poly-logarithmic approximation ratio for the non-uniform problem that allows different cost functions on each edge and node; the ratio we achieve is $O(\log^4 h)$, where h is the number of demand pairs. In addition we present an $O(\log h)$ approximation for the single sink problem. Poly-logarithmic ratios for some related problems are also obtained. Our algorithm for the multicommodity problem is obtained via a reduction to the single source problem using the notion of junction trees. We believe that this presents a simple yet useful general technique for network design problems.

We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that each point p ∈ P is covered by (contained in) at least demands d(p) sets. Here demands d(p) is an integer demand (requirement) for p. When the demands demands d(p)=1 for all p, this is the standard set cover problem. The set cover problem in geometric settings admits an approximation ratio that is better than that for the general version. In this paper, we show that similar improvements can be obtained for the multi-cover problem as well. In particular, we obtain an O(log Opt) approximation for set systems of bounded VC-dimension, and an O(1) approximation for covering points by half-spaces in three dimensions and for some other classes of shapes.

In this paper, we propose greedy selection rounding (GSR), an efficient and near-optimal algorithm to design a wireless mesh network topology that maximizes the coverage of the users while ensuring that the network is resilient to node failures and and the deployment cost is under a given budget. In the case that GSR fails to find a solution satisfying the budget constraint, the incurred cost does not exceed the budget by a constant factor. Through extensive evaluation, we show that in all our test cases GSR always generates a topology above 95% of the optimal in terms of the number of covered users while never exceeding the budget by more than 15%.

In this paper two scheduling models are addressed. First is the standard model (unicast) where requests (or jobs) are independent. The other is the broadcast model where broadcasting a page can satisfy multiple outstanding requests for that page. We consider online scheduling of requests when they have deadlines. Unlike previous models, which mainly consider the objective of maximizing throughput while respecting deadlines, here we focus on scheduling all the given requests with the goal of minimizing the maximum delay factor. The delay factor of a schedule is defined to be the minimum α ≥ 1 such that each request i is completed by time ai + α(di – ai) where ai is the arrival time of request i and di is its deadline. Delay factor generalizes the previously defined measure of maximum stretch which is based only the processing times of requests [9, 11]. We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis [24] and prove the following positive results. For the unicast model we give algorithms that are (1 + ∊)-speed -competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for same-sized pages that is (2 + ∊)-speed -competitive. For arbitrary page sizes we give an algorithm that is (4 + ∊)-speed -competitive.

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.

Given an edge-weighted undirected graph $G$ with a specified set of terminals, let the \emph{density} of any subgraph be the ratio of its weight/cost to the number of terminals it contains. If $G$ is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of $G$? We answer this question in the affirmative by giving an algorithm to \emph{prune} $G$ and find such subgraphs of any desired size, at the cost of only a logarithmic increase in density (plus a small additive factor). We apply the pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the \kv problem, we are given an undirected graph $G$ with edge costs and an integer $k$; the goal is to find a minimum-cost 2-vertex-connected subgraph of $G$ containing at least $k$ vertices. In the \bv\ problem, we are given the graph $G$ with edge costs, and a budget $B$; the goal is to find a 2-vertex-connected subgraph $H$ of $G$ with total edge cost at most $B$ that maximizes the number of vertices in $H$. We describe an $O(\log n \log k)$ approximation for the \kv problem, and a bicriteria approximation for the \bv\ problem that gives an $O(\frac{1}{\eps}\log^2 n)$ approximation, while violating the budget by a factor of at most $3+\eps$.

We study single-sink network design problems in undirected graphs with vertex connectivity requirements. The input to these problems is an edge-weighted undirected graph $G=(V,E)$, a sink/root vertex $r$, a set of terminals $T \subseteq V$, and integer $k$. The goal is to connect each terminal $t \in T$ to $r$ via $k$ \emph{vertex-disjoint} paths. In the {\em connectivity} problem, the objective is to find a min-cost subgraph of $G$ that contains the desired paths. There is a $2$-approximation for this problem when $k \le 2$ \cite{FleischerJW} but for $k \ge 3$, the first non-trivial approximation was obtained in the recent work of Chakraborty, Chuzhoy and Khanna \cite{ChakCK08}; they describe and analyze an algorithm with an approximation ratio of $O(k^{O(k^2)}\log^4 n)$ where $n=|V|$. In this paper, inspired by the results and ideas in \cite{ChakCK08}, we show an $O(k^{O(k)}\log |T|)$-approximation bound for a simple greedy algorithm. Our analysis is based on the dual of a natural linear program and is of independent technical interest. We use the insights from this analysis to obtain an $O(k^{O(k)}\log |T|)$-approximation for the more general single-sink {\em rent-or-buy} network design problem with vertex connectivity requirements. We further extend the ideas to obtain a poly-logarithmic approximation for the single-sink {\em buy-at-bulk} problem when $k=2$ and the number of cable-types is a fixed constant; we believe that this should extend to any fixed $k$. We also show that for the non-uniform buy-at-bulk problem, for each fixed $k$, a small variant of a simple algorithm suggested by Charikar and Kargiazova \cite{CharikarK05} for the case of $k=1$ gives an $2^{O(\sqrt{\log |T|})}$ approximation for larger $k$. These results show that for each of these problems, simple and natural algorithms that have been developed for $k=1$ have good performance for small $k > 1$.

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.

We consider a multicast game with selfish non- cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium. The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with in players, we establish an upper bound of O(radicnlog2n) on the price of anarchy, and a lower bound of Omega(log n/log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

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

The approximability of the maximum edge-disjoint paths problem (EDP) in directed graphs was seemingly settled by an Ω( m 1/2 - ϵ)-hardness result of Guruswami et al. [2003], and an O (√ m ) approximation achievable via a natural multicommodity-flow-based LP relaxation as well as a greedy algorithm. Here m is the number of edges in the graph. We observe that the Ω( m 1/2 - ϵ)-hardness of approximation applies to sparse graphs, and hence when expressed as a function of n , that is, the number of vertices, only an Ω( n 1/2 - ϵ)-hardness follows. On the other hand, O (√ m )-approximation algorithms do not guarantee a sublinear (in terms of n ) approximation algorithm for dense graphs. We note that a similar gap exists in the known results on the integrality gap of the flow-based LP relaxation: an Ω(√ n ) lower bound and O (√ m ) upper bound. Motivated by this discrepancy in the upper and lower bounds, we study algorithms for EDP in directed and undirected graphs and obtain improved approximation ratios. We show that the greedy algorithm has an approximation ratio of O (min( n 2/3 , √ m )) in undirected graphs and a ratio of O (min( n 4/5 , √ m )) in directed graphs. For acyclic graphs we give an O (√ n ln n ) approximation via LP rounding. These are the first sublinear approximation ratios for EDP. The results also extend to EDP with weights and to the uniform-capacity unsplittable flow problem (UCUFP).

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 consider approximation algorithms for non-uniform buy-at-bulk network design problems. The first non-trivial approximation algorithm for this problem is due to Charikar and Karagiozova (STOC 05); for an instance on h pairs their algorithm has an approximation guarantee of exp(O(radic(log h log log h)))for the uniform-demand case, and log D middot exp(O(radic(log h log log h))) for the general demand case, where D is the total demand. We improve upon this result, by presenting the first poly-logarithmic approximation for this problem. The ratio we obtain is O(log3h middot min{log D, gamma(h2)}) where his the number of pairs and gamma(n) is the worst case distortion in embedding the metric induced by a n vertex graph into a distribution over its spanning trees. Using the best known upper bound on gamma(n) we obtain an O(min{log3h middot log D, log5h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the single-source problem that we need for the multicommodity problem

A non-uniform demand network consists of a source and a set of receivers that have different min-cut values from the source. We look at the case where each receiver would like to receive information from the source at a rate that is equal to its min-cut value. This problem has been formulated before, and in contrast to the uniform case, it has been shown that the non-uniform case does not admit a good characterization. Motivated by this, we formulate relaxations of the problem and present some preliminary results

We consider a multicast game with selfish non-cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium.The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of O(√n log2n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

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 consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph $G=(V, E)$, a subset of vertices $X \subseteq V$ called {\em terminals}, and an integer $k \le |X|$, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy $(2-\frac{2}{k})$-approximation based on Gomory--Hu trees, and a $(2 - \frac{2}{|X|})$-approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with $k=2$).

We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion and hence also embedded into $\ell_1$ with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs and include the family of weighted $k\times n$ planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outerplanar graphs, thus extending a theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24(2004), pp. 233-269] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We conjecture that these embeddings for k-outerplanar graphs may serve as building blocks for $\ell_1$ embeddings of more general metrics.

We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard linear programming formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to /spl radic/N. We also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.

Given an arc-weighted directed graph G = (V, A, /spl lscr/) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, N et al. (2004)] is O(log/sup 2/ OPT). The second application is an O(log/sup 2/ k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log/sup 2/ k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, N et al.) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than /spl Omega/(log/sup 1-/spl epsi// OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.

We examine the throughput benefits that network coding offers with respect to the average through- put achievable by routing, where the average throughput refers to the average of the rates that the indi- vidual receivers experience. We relate these benefits to the integrality gap of a standard LP formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with N receivers where network coding offers benefits proportional to √N. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.

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

The emerging multiprotocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP, and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: 1) no backtracking (D=0); 2) limited backtracking (D=k); and 3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link-state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.

The multiple knapsack problem (MKP) is a natural and well-known generalization of the single knapsack problem and is defined as follows. We are given a set of n items and m bins (knapsacks) such that each item i has a profit $p(i)$ and a size $s(i)$, and each bin j has a capacity $c(j)$. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the bins. MKP is a special case of the generalized assignment problem (GAP) where the profit and the size of an item can vary based on the specific bin that it is assigned to. GAP is APX-hard and a 2-approximation, for it is implicit in the work of Shmoys and Tardos [Math. Program. A, 62 (1993), pp. 461-474], and thus far, this was also the best known approximation for MKP\@. The main result of this paper is a polynomial time approximation scheme (PTAS) for MKP\@. Apart from its inherent theoretical interest as a common generalization of the well-studied knapsack and bin packing problems, it appears to be the strongest special case of GAP that is not APX-hard. We substantiate this by showing that slight generalizations of MKP are APX-hard. Thus our results help demarcate the boundary at which instances of GAP become APX-hard. An interesting aspect of our approach is a PTAS-preserving reduction from an arbitrary instance of MKP to an instance with $O(\log n)$ distinct sizes and profits.

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 investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their Lp norms, for any fixed p ≥ 1.

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

Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications. The goal is to efficiently maintain clusters of small diameter as new points are inserted. We analyze several natural greedy algorithms and demonstrate that they perform poorly. We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance, and which we believe should also perform well in practice. We complement our positive results with lower bounds on the performance of incremental algorithms. Finally, we consider the dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.

We study the approximability of multidimensional generalizations of three classical packing problems: multiprocessor scheduling, bin packing, and the knapsack problem. Specifically, we study the vector scheduling problem, its dual problem, namely, the vector bin packing problem, and a class of packing integer programs. The vector scheduling problem is to schedule nd -dimensional tasks on m machines such that the maximum load over all dimensions and all machines is minimized. The vector bin packing problem, on the other hand, seeks to minimize the number of bins needed to schedule all n tasks such that the maximum load on any dimension across all bins is bounded by a fixed quantity, say, 1. Such problems naturally arise when scheduling tasks that have multiple resource requirements. Finally, packing integer programs capture a core problem that directly relates to both vector scheduling and vector bin packing, namely, the problem of packing a maximum number of vectors in a single bin of unit height. We obtain a variety of new algorithmic as well as inapproximability results for these three problems.

We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616--630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448--455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652--658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric, thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of $2+\sqrt{2}\simeq 3.414$ for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric.

The emerging multi-protocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites (see Davie, B. and Rekhter, Y., 2000; Awduche, D. et. al., 1999; Sharma, V. et al., 2002; Jamoussi et al., 2002). This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along the primary path fail. We address the problem of distributed routing of restoration paths, defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance, D: (1) no backtracking (D=0); (2) limited backtracking (D=k); (3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.

(MATH) We present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a (1+e)-approximate solution for any instance of weighted flow time in O(nO(ln W ln P/e3)) time; here P is the ratio of maximum job processing time to minimum job processing time, and W is the ratio of maximum job weight to minimum job weight. This result directly gives a quasi-PTAS for weighted flow time when P and W are poly-bounded, and a PTAS when they are both O(1). We strengthen the former result to show that in order to get a quasi- PTAS it suffices to have just one of P and W to be poly-bounded. Our result provides strong evidence to the hypothesis that the weighted flow time problem has a PTAS. We note that the problem is strongly NP-hard even when P and W are O(1). We next consider two important special cases of weighted flow time, namely, when P is O(1) and W is arbitrary, and when the weight of a job is inverse of its processing time referred to as the stretch metric. For both of the above special cases we obtain a (1+e)-approximation for any e ρ 0 by using a randomized partitioning scheme to reduce an arbitrary instance to several instances all of which have P and W bounded by a constant that depends only on e.

We study the problem of minimizing weighted flow time on a single machine in the preemptive setting. We present an O(\log^2 P)-competitive semi-online algorithm where P is the ratio of the maximum and minimum processing times of jobs in the system. In the offline setting we show that a (2+\eps)-approximation is achievable in quasi-polynomial time. These are the first non-trivial results for the weighted versions of minimizing flow time. For multiple machines we show that no competitive randomized online algorithm exists for weighted flow time. We also present an improved online algorithm for minimizing total stretch (a special case of weighted flow time) on multiple machines.

We consider the problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints. Recent work has led to constant-factor approximations for this problem based on solving a preemptive or linear programming relaxation and then using the solution to get an ordering on the jobs. We introduce several new techniques which generalize this basic paradigm. We use these ideas to obtain improved approximation algorithms for one-machine scheduling to minimize average completion time with release dates. In the process, we obtain an optimal randomized on-line algorithm for the same problem that beats a lower bound for deterministic on-line algorithms. We consider extensions to the case of parallel machine scheduling, and for this we introduce two new ideas: first, we show that a preemptive one-machine relaxation is a powerful tool for designing parallel machine scheduling algorithms that simultaneously produce good approximations and have small running times; second, we show that a nongreedy "rounding" of the relaxation yields better approximations than a greedy one. We also prove a general theorem relating the value of one-machine relaxations to that of the schedules obtained for the original m-machine problems. This theorem applies even when there are precedence constraints on the jobs. We apply this result to obtain improved approximation ratios for precedence graphs such as in-trees, out-trees,and series-parallel graphs.

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n 3 ). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the APSP problem in unweighted, undirected graphs with an additive error of 2 in time $O(n^{2.5}\sqrt{\log n})$. This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time {\footnotesize $O(n^{1.5} \sqrt{k \log n} + n^2 \log^2 n)$} for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an $O(m \sqrt{n \log n})$ algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2/3 approximation to the diameter in time $O(m \sqrt{n \log n} + n^2 \log n)$. Unlike in the case of APSP, our results for approximate diameter computation can be extended to the case of directed graphs with arbitrary positive real weights on the edges.

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Article Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median Share on Authors: Moses Charikar Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Chandra Chekuri Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Ashish Goel Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile , Sudipto Guha Computer Science Department, Stanford University Computer Science Department, Stanford UniversityView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 114–123https://doi.org/10.1145/276698.276719Online:23 May 1998Publication History 96citation795DownloadsMetricsTotal Citations96Total Downloads795Last 12 Months33Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space.We propose a model-c~led incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications.The goal is to efficiently maintain clusters of small diameter as new points are inserted.We analyze several natural greedy algorithms and demonstrate that they perform poorly.We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance.We complement our positive results with lower bounds on the performance of incremental algorithms.Finally, we consider tbe dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.

Code scheduling to exploit instruction level parallelism (ILP) is a critical problem in compiler optimization research in light of the increased use of long-instruction-word machines. Unfortunately optimum scheduling is computationally intractable, and one must resort to carefully crafted heuristics in practice. If the scope of application of a scheduling heuristic is limited to basic blocks, considerable performance loss may be incurred at block boundaries. To overcome this obstacle, basic blocks can be coalesced across branches to form larger regions such as super blocks. In the literature, these regions are typically scheduled using algorithms that are either oblivious to profile information (under the assumption that the process of forming the region has fully utilized the profile information), or use the profile information as an addendum to classical scheduling techniques. We believe that even for the simple case of linear code regions such as super blocks, additional performance improvement can be gained by utilizing the profile information in scheduling as well. We propose a general paradigm for converting any profile-insensitive list scheduler to a profile-sensitive scheduler. Our technique is developed via a theoretical analysis of a simplified abstract model of the general problem of profile-driven scheduling over any acyclic code region, yielding a scoring measure for ranking branch instructions.

We introduce a class of novel multiprocessor scheduling problems that arise in the optimization of SQL queries for