We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph \(G\), compute a vertex-cut \((L, S, R)\) in \(G\) of minimum value, which is defined to be the total weight of all vertices in \(S\). The problem, together with its edge-based variant, is one of the most basic in graph theory and algorithms, and has been studied extensively. The fastest currently known algorithm for directed global minimum vertex-cut (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) has running time \(\tilde{O}(mn)\), where \(m\) and \(n\) denote the number of edges and vertices in the input graph, respectively. A long line of work over the past decades led to faster algorithms for other main versions of the problem, including the undirected edge-based setting (Karger, STOC 1996 and J. ACM 2000), directed edge-based setting (Cen et al., FOCS 2021), and undirected vertex-based setting (Chuzhoy and Trabelsi, STOC 2025). However, for the vertex-based version in directed graphs, the 29 year-old \(\tilde{O}(mn)\)-time algorithm of Henzinger, Rao and Gabow remains the state of the art to this day, in all edge-density regimes.

In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions, while minimizing the update time. The problem has been studied extensively in the oblivious-adversary setting, where randomized algorithms with polylogarithmic worst-case and constant amortized update time have been known for some time. A major challenge in this area has been designing an algorithm with non-trivial update time against an adaptive adversary, who may explicitly tailor the update sequence to the algorithm’s choices. In a recent breakthrough, Bernstein, Bhattacharya, Kiss, and Saranurak (STOC 2025; hereafter, BBKS25) obtained the first algorithms with sublinear in n update time for this setting: namely, a randomized algorithm with Õ(n3/4) amortized update time, and a deterministic algorithm with Õ(n8/9) amortized update time. Our main result is a deterministic algorithm for fully dynamic maximal matching with amortized update time n1/2+o(1).

A t-spanner of an undirected n-vertex graph G is a sparse subgraph H of G that preserves all pairwise distances between its vertices to within multiplicative factor t, also called the stretch. Spanners play an important role in the design of efficient algorithms for distance-based graph optimization problems, as they allow one to sparsify the graph, while approximately preserving all distances. It is well known that any n-vertex graph admits a (2k — 1)-spanner with O (n1+1/k) edges, and that this stretch-size tradeoff is optimal assuming the Erdos Girth Conjecture. In this paper we investigate the problem of efficiently maintaining spanners in the fully dynamic setting with an adaptive adversary. Despite a long and intensive line of research, this problem is still poorly understood: for example, no algorithm achieving a sublogarithmic stretch, with a sublinear in n update time, and a strongly subquadratic in n bound on the size of the spanner is currently known in this setting. One of our main results is a deterministic (and therefore, adaptive-adversary) algorithm, that, for any 512 ≤ k ≤ (log n )1/49 and 1/k ≤ δ ≤ 1/400, maintains a spanner H of a fully dynamic graph with stretch poly(k ) · 2o (1/δ6) and size |E (H )| ≤ O (n 1+O (1/k )), with worst-case update time n O(δ ) and recourse n O(1/k ).

The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp [26] shows that maximum bipartite matching can be solved in O(m√n) time on a graph with n vertices and m edges. For the case of very dense graphs, a different approach based on fast matrix multiplication was subsequently developed [27, 39], that achieves a running time of O(n2.371). For the next several decades, these results represented the fastest known algorithms for the problem until in 2013, a ground-breaking work of Madry [36] gave a significantly faster algorithm for sparse graphs. Subsequently, a sequence of works developed increasingly faster algorithms for solving maximum bipartite matching, and more generally directed maximum flow, culminating in a spectacular recent breakthrough [9] that gives an m1+o(1) time algorithm for maximum bipartite matching (and more generally, for min cost flows). These more recent developments collectively represented a departure from earlier combinatorial approaches: they all utilized continuous techniques based on interior-point methods for solving linear programs.

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an O(m √n)-time algorithm for the problem, where n and m are the number of vertices and edges in the input graph, respectively. For dense graphs, an approach based on fast matrix multiplication achieves a running time of O(n2.371). For several decades, these results represented state-of-the-art algorithms, until, in 2013, Madry introduced a powerful new approach for solving MBM using continuous optimization techniques. This line of research, that builds on continuous techniques based on interior-point methods, led to several spectacular results, culminating in a breakthrough m1+o(1)-time algorithm for min-cost flow, that implies an m1+o(1)-time algorithm for MBM as well. These striking advances naturally raise the question of whether combinatorial algorithms can match the performance of the algorithms that are based on continuous techniques for MBM. One reason to explore combinatorial algorithms is that they are often more transparent than their continuous counterparts, and that the tools and techniques developed for such algorithms may be useful in other settings, including, for example, developing faster algorithms for maximum matching in general graphs. A recent work of Chuzhoy and Khanna (2024) made progress on this question by giving a combinatorial Õ(m1/3n5/3)-time algorithm for MBM, thus outperforming both the Hopcroft-Karp algorithm and matrix multiplication based approaches, on sufficiently dense graphs. Still, a large gap remains between the running time of their algorithm and the almost linear-time achievable by algorithms based on continuous techniques. In this work, we take another step towards narrowing this gap, and present a randomized n2+o(1)-time combinatorial algorithm for MBM. Thus in dense graphs, our algorithm essentially matches the performance of algorithms that are based on continuous methods. Similar to the classical algorithms for MBM and the approach used in the work of Chuzhoy and Khanna (2024), our algorithm is based on iterative augmentation of a current matching using augmenting paths in the corresponding (directed) residual flow network. Our main contribution is a recursive algorithm that exploits the special structure of the resulting flow problem to recover an Ω(1/log2 n)-fraction of the remaining augmentations in n2+o(1) time. Finally, we obtain a randomized n2+o(1)-time algorithm for maximum vertex-capacitated s-t flow in directed graphs when all vertex capacities are identical, using a standard reduction from this problem to MBM.

We propose a new conjecture on hardness of 2-CSP’s, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP’s that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP’s in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

Expander graphs play a central role in graph theory and algorithms. With a number of powerful algorithmic tools developed around them, such as the Cut-Matching game, expander pruning, expander decomposition, and algorithms for decremental All-Pairs Shortest Paths (APSP) in expanders, to name just a few, the use of expanders in the design of graph algorithms has become ubiquitous. Specific applications of interest to us are fast deterministic algorithms for cut problems in static graphs, and algorithms for dynamic distance-based graph problems, such as APSP.

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglogn)2O(1/є3), and has amortized update time O(nєlogL) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O(2O(1/є)· logn· loglogL), and query time for shortest-path query is O(|E(P)|+2O(1/є)· logn· loglogL), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Θ(m) amortized update time and better than Θ(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.

We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))-approximation, for a small fixed constant є, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O(2O((logn)7/8loglogn)·(Δ))-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n).

In the classical node-disjoint paths (\sf NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection ${\mathcal M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$, while the best previous negative result is an $\Omega(\log^{1/2-\delta}n)$-hardness of approximation for any constant $\delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$. The best previous lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper, we prove that \sf NDP is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in \sf NP have algorithms with running time $n^{O(\log n)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related edge-disjoint paths (\sf EDP) problem, showing the same hardness of approximation ratio even for subcubic planar graphs with all sources lying on the boundary of a single face.

In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph G = (V, E) with n vertices and m edges undergoing edge deletions, together with a fixed source vertex s ∊ V. The goal is to maintain a data structure that supports shortest-path queries: given a vertex v ∊ V, quickly return an (approximate) shortest path from s to v. The decremental all-pairs shortest paths (APSP) problem is defined similarly, but now the shortest-path queries are allowed between any pair of vertices of V. Both problems have been studied extensively since the 80's, and algorithms with near-optimal total update time and query time have been discovered for them. Unfortunately, all these algorithms are randomized and, more importantly, they need to assume an oblivious adversary – a drawback that prevents them from being used as subroutines in several known algorithms for classical static problems. In this paper, we provide new deterministic algorithms for both problems, which, by definition, can handle an adaptive adversary. Our first result is a deterministic algorithm for the decremental SSSP problem on weighted graphs with O(n2+o(1)) total update time, that supports (1 + ∊)-approximate shortest-path queries, with query time O(|P| · no(1)), where P is the returned path. This is the first (1 + ∊)-approximation adaptive-update algorithm supporting shortest-path queries in time below O(n), that breaks the O(mn) total update time bound of the classical algorithm of Even and Shiloah from 1981. Previously, Bernstein and Chechik [STOC'16, ICALP'17] provided a Õ(n2)-time deterministic algorithm that supports approximate distance queries, but unfortunately the algorithm cannot return the approximate shortest paths. Chuzhoy and Khanna [STOC'19] showed an O(n2+o(1))-time randomized algorithm for SSSP that supports approximate shortest-path queries in the adaptive adversary regime, but their algorithm only works in the restricted setting where only vertex deletions, and not edge deletions are allowed, and it requires Ω(n) time to respond to shortest-path queries. Our second result is a deterministic algorithm for the decremental APSP problem on unweighted graphs that achieves total update time O(n2.5+δ), for any constant δ > 0, supports approximate distance queries in O(log log n) time, and supports approximate shortest-path queries in time O(|E(P)| · no(1)), where P is the returned path; the algorithm achieves an O(1)-multiplicative and no(1)-additive approximation on the path length. All previous algorithms for APSP either assume an oblivious adversary or have an Ω(n3) total update time when m = Ω(n2), even if an o(n)-multiplicative approximation is allowed. To obtain both our results, we improve and generalize the layered core decomposition data structure introduced by Chuzhoy and Khanna to be nearly optimal in terms of various parameters, and introduce a new generic approach of rooting Even-Shiloach trees at expander sub-graphs of the given graph. We believe both these technical tools to be interesting in their own right and anticipate them to be useful for designing future dynamic algorithms that work against an adaptive adversary.

We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an undirected n-vertex m-edge graph G with non-negative lengths on edges, that undergoes an online sequence of edge deletions. The goal is to support approximate shortest-paths queries: given a pair x,y of vertices of G, return a path P connecting x to y, whose length is within factor α of the length of the shortest x-y path, in time Õ(|E(P)|), where α is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems.

The dynamic optimality conjecture, postulating the existence of an $O(1)$-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known $O(\log \log n)$-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an $O(\log \log n)$-approximation, even in the offline setting. All known non-trivial algorithms for BST's so far rely on comparing the algorithm's cost with the so-called Wilber's first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as $Ω(\log \log n/ \log \log \log n)$; in fact, the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer $D>0$, obtains an $O(D)$-approximation in time $\exp\left(O\left (n^{1/2^{Ω(D)}}\log n\right )\right )$. In particular, this gives a constant-factor approximation sub-exponential time algorithm. Moreover, we obtain a simpler and cleaner efficient $O(\log \log n)$-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call {\em Guillotine Bound}, that is stronger than WB, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1 ≤ r ≤ O(logn), computes a (logm)r2-approximation for Minimum Balanced Cut in G, in time O(m1+O(1/r)+o(1)·(logm)O(r2)). In particular, we obtain a (logm)1/ε-approximation in time m1+O(√{ε})for any constant , and a (logm)f(m)-approximation in time m1+o(1), for any slowly growing function f(m). We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is no(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges. The problem is notoriously difficult, and despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a Õ̃(√n)-approximation, while the best current negative results do not rule out constantfactor approximation. All current approximation algorithms for the problem build on the same paradigm, which is also used in practice: compute a set E' of edges (called a planarizing set) such that G \ E' is planar; compute a planar drawing of G\E'; then add the drawings of the edges of E' to the resulting drawing. Unfortunately, there are examples of graphs G, in which any implementation of this method must incur Ω(OPT2) crossings, where OPT is the value of the optimal solution. This barrier seems to doom the only currently known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than O(√n)-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm, that, given a bounded-degree graph G and a planarizing set E' of its edges, computes another planarizing edge set E'' with E' ⊆ E'', such that |E''| is relatively small, and there exists a nearoptimal drawing of G in which no edges of G \ E'' participate in crossings. This allows us to reduce the Crossing Number problem to Crossing Number with Rotation System - a variant of the Crossing Number problem, in which the ordering of the edges incident to every vertex is fixed as part of input. In our reduction, we obtain an instance G' of this problem, where |E(G')| is roughly bounded by the crossing number of the original graph G. We show a randomized algorithm for this new problem, that allows us to obtain an O(n1/2-ε)approximation for Graph Crossing Number on bounded-degree graphs, for some constant ε > 0.

Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every k-edge connected graph G contains a collection 𝒯 of ⌊k/2⌋ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing 𝒯 is the largest diameter of any tree in 𝒯. A desirable property of a tree packing for leveraging the high connectivity of a graph in distributed communication networks, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing of a low-diameter graph G, whose diameter is sublinear in |V(G)|, or, alternatively, how to show that such a packing does not exist. In this paper, we provide first non-trivial upper and lower bounds on the diameter of tree packing. We start by showing that, for every k-edge connected n-vertex graph G of diameter D, there is a tree packing 𝒯 containing Ω(k) trees, of diameter O((101k log n)^D), with edge-congestion at most 2. Karger’s edge sampling technique demonstrates that, if G is a k-edge connected graph, and G[p] is a subgraph of G obtained by sampling each edge of G independently with probability p = Θ(log n/k), then with high probability G[p] is connected. We extend this result to show that the diameter of G[p] is bounded by O(k^(D(D+1)/2)) with high probability. This immediately gives a tree packing of Ω(k/log n) edge-disjoint trees of diameter at most O(k^(D(D+1)/2)). We also show that these two results are nearly tight for graphs with a small diameter: we show that there are k-edge connected graphs of diameter 2D, such that any packing of k/α trees with edge-congestion η contains at least one tree of diameter Ω((k/(2α η D))^D), for any k,α and η. Additionally, we show that if, for every pair u,v of vertices of a given graph G, there is a collection of k edge-disjoint paths connecting u to v, of length at most D each, then we can efficiently compute a tree packing of size k, diameter O(D log n), and edge-congestion O(log n). Finally, we provide several applications of low-diameter tree packing in the distributed settings of network optimization and secure computation.

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function f : ℤ+ → ℤ+, such that for every integer g > 0, every graph of treewidth at least f(g) contains the (g × g)-grid as a minor. For every integer g > 0, let f(g) be the smallest value for which the theorem holds. Establishing tight bounds on f(g) is an important graph-theoretic question. Robertson and Seymour showed that f(g) = Ω(g2 log g) must hold. For a long time, the best known upper bounds on f(g) were super-exponential in g. The first polynomial upper bound of f(g) = O(g98 poly log g) was proved by Chekuri and Chuzhoy. It was later improved to f(g) = O(g36 poly log g), and then to f(g) = O(g19 poly log g). In this paper we further improve this bound to f(g) = O(g9 poly log g). We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on f(g).

We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph G=(V,E) with lengths ℓ(e)≥ 1 on its edges that undergoes vertex deletions, and a source vertex s, we need to support (approximate) shortest-path queries in G: given a vertex v, return a path connecting s to v, whose length is at most (1+є) times the length of the shortest such path, where є is a given accuracy parameter. The problem has many applications, for example to flow and cut problems in vertex-capacitated graphs. Decremental SSSP is a fundamental problem in dynamic algorithms that has been studied extensively, especially in the more standard edge-decremental setting, where the input graph G undergoes edge deletions. The classical algorithm of Even and Shiloach supports exact shortest-path queries in O(mn) total update time. A series of recent results have improved this bound to O(m1+o(1)logL), where L is the largest length of any edge. However, these improved results are randomized algorithms that assume an oblivious adversary. To go beyond the oblivious adversary restriction, recently, Bernstein, and Bernstein and Chechik designed deterministic algorithms for the problem, with total update time Õ(n2logL), that by definition work against an adaptive adversary. Unfortunately, their algorithms introduce a new limitation, namely, they can only return the approximate length of a shortest path, and not the path itself. Many applications of the decremental SSSP problem, including the ones considered in this paper, crucially require both that the algorithm returns the approximate shortest paths themselves and not just their lengths, and that it works against an adaptive adversary. Our main result is a randomized algorithm for vertex-decremental SSSP with total expected update time O(n2+o(1)logL), that responds to each shortest-path query in Õ(nlogL) time in expectation, returning a (1+є)-approximate shortest path. The algorithm works against an adaptive adversary. The main technical ingredient of our algorithm is an Õ(|E(G)|+ n1+o(1))-time algorithm to compute a core decomposition of a given dense graph G, which allows us to compute short paths between pairs of query vertices in G efficiently. We use our result for vertex-decremental SSSP to obtain (1+є)-approximation algorithms for maximum s-t flow and minimum s-t cut in vertex-capacitated graphs, in expected time n2+o(1), and an O(log4n)-approximation algorithm for the vertex version of the sparsest cut problem with expected running time n2+o(1). These results improve upon the previous best known algorithms for these problems in the regime where m= ω(n1.5 + o(1)).

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy $O(\sqrt{n})$-approximation algorithm. A special case of the problem called NDP-Grid, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for NDP-Grid achieves an $\tilde{O}(n^{1/4})$-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor $2^{Ω(\sqrt{\log n})}$, even if the underlying graph is a sub-graph of a grid, and all source vertices lie on the grid boundary. In a follow-up work, the authors further show that NDP-Grid is hard to approximate to within factor $Ω(2^{\log^{1-ε}n})$ for any constant $ε$ under standard complexity assumptions, and to within factor $n^{Ω(1/(\log\log n)^2)}$ under randomized ETH. In this paper we study NDP-Grid, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized $2^{O(\sqrt{\log n} \cdot \log\log n)}$-approximation algorithm for this problem. We generalize this result to instances where the source vertices lie within a prescribed distance from the grid boundary. Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an $Ω(\sqrt n)$ integrality gap, even in grid graphs. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.

In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G=(V,E), and a collection M={(s1,t1),…,(sk,tk)} of pairs of its vertices, called source-destination, or demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices. The best current algorithm for NDP achieves an O(√n)-approximation, while, until recently, the best negative result was a factor Ω(log1/2−єn)-hardness of approximation, for any constant є, unless NP ⊆ ZPTIME(npoly logn). In a recent work, the authors have shown an improved 2Ω(√logn)-hardness of approximation for NDP, unless NP⊆ DTIME(nO(logn)), even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. Unfortunately, this result does not extend to grid graphs.

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected n-vertex graph G, and a collection M={(s1,t1),…,(sk,tk)} of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is O(√n), while the best current negative result is an Ω(log1/2-δn)-hardness of approximation for any constant δ, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an Õ(n1/4)-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is Õ(n9/19). The best currently known lower bound for both these versions of the problem is APX-hardness.

This special section comprises ten fully refereed papers whose extended abstracts were presented at the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014) in Philadelphia, Pennsylvania, October 19--21, 2014. The unrefereed conference versions of these papers were published by IEEE in the FOCS 2014 proceedings. The regular conference program consisted of 68 papers chosen from among 273 submissions. These were selected by a program committee consisting of Scott Aaronson, Boaz Barak, Nikhil Bansal, Timothy Chan, Moses Charikar, Shuchi Chawla, Julia Chuzhoy, Andrew Drucker, Valerie King, Robert Kleinberg, Eyal Kushilevitz, James R. Lee, Aleksander Maͅdry, Raghu Meka, Ankur Moitra, Aaron Roth, Alexander Russell, David Steurer, Madhu Sudan, Kunal Talwar, Brent Waters, Ryan Williams, and David Woodruff. The program committee was chaired by Boaz Barak. The papers invited to this special section were also selected with the input of the program committee. The ten papers in this section span a broad range of topics, including fixed-parameter tractability, online algorithms, combinatorics, coding theory, sublinear algorithms, approximation algorithms, hardness of approximation, dynamic algorithms, algebraic complexity and probability theory. Each paper underwent an extensive refereeing process; we thank both the authors and the anonymous referees for their efforts. In addition, we would like to thank SICOMP Editor-in-Chief Leonard Schulman and SIAM Senior Publications Coordinator Heather Blythe for their help in preparing this special section.

We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of n axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no two of them overlap. MISR is a basic geometric optimization problem with many applications, that has been studied extensively. Until recently, the best approximation algorithm for it achieved an O(log log n)-approximation factor. In a recent breakthrough, Adamaszek and Wiese provided a quasi-polynomial time approximation scheme: a (1-ε)-approximation algorithm with running time nO(poly(log n)/ε). Despite this result, obtaining a PTAS or even a polynomial-time constant-factor approximation remains a challenging open problem. In this paper we make progress towards this goal by providing an algorithm for MISR that achieves a (1 - ε)-approximation in time nO(poly(log logn/ε)). We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.

We study the classical Node-Disjoint Paths (NDP) problem: given an n-vertex graph G and a collection =(s1,t1),…,(sk,tk) of pairs of vertices of G called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of O(√n) on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than Ω(log1/2−δn)-approximation for any constant δ, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is Ω(√n) for NDP, even in planar graphs. In this paper, we break the barrier of O(√n) on the approximability of NDP in planar graphs and obtain an Õ(n9/19)-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

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 .

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n -vertex graph G , a collection M ={ ( s 1 , t 1 ),… ,( s k , t k ) } of pairs of vertices called demand pairs, and an integer c . The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c . When the maximum allowed congestion is c = 1, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an O (√ n )-approximation by rounding the standard multi-commodity flow relaxation of the problem. This matches the Ω (√ n ) lower bound on the integrality gap of this relaxation. We show an O (poly log k )-approximation algorithm for EDPwC with congestion c = 2 by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of ~ Ω ((log n ) 1/( c +1) ) for any constant congestion c . Prior to our work, the best approximation factor for EDPwC with congestion 2 was Õ( n 3/7 ), and the best algorithm achieving a polylogarithmic approximation required congestion 14.

Given an undirected graph $G=(V,E)$, a collection $\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of $k$ pairs of its vertices, called demand pairs, and an integer $c$, the goal in the Edge-Disjoint Paths with Congestion problem is to connect the maximum possible number of demand pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed $c$. We show an efficient randomized algorithm to route $\Omega(\mathsf{OPT}/{\operatorname{poly}}\log k)$ demand pairs with congestion at most 14, where $\mathsf{OPT}$ is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The algorithm in fact routes $\Omega({\mathsf{OPT}_{\mathsf{LP}}}/{\operatorname{poly}}\log k)$ pairs, where ${\mathsf{OPT}_{\mathsf{LP}}}$ is the optimal value of the standard multicommodity flow relaxation for the problem. The best previous efficient algorithm that routed $\Omega(\mathsf{OPT}/{\operatorname{poly}}\log n)$ pairs required congestion ${\operatorname{poly}}(\log \log n)$, and for the setting where the maximum allowed congestion is bounded by a constant $c$, the best previous efficient algorithms could only guarantee the routing of $\Omega(\mathsf{OPT}/n^{1/c})$ pairs. We also introduce a new type of vertex sparsifier that we call an integral flow sparsifier; integral flow sparsifiers approximately preserve both fractional and integral routings. We show an algorithm that constructs such sparsifiers.

We study the k -route cut problem: given an undirected edge-weighted graph G = ( V , E ), a collection {( s 1 , t 1 ), ( s 2 , t 2 ), …, ( s r , t r )} of source-sink pairs, and an integer connectivity requirement k , the goal is to find a minimum-weight subset E ′ of edges to remove, such that the connectivity of every pair ( s i , t i ) falls below k . Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most ( k − 1) edge-disjoint paths connecting s i to t i in G ∖ E ′, while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithms have been known for the special case where k ⩽ 3, but no non-trivial approximation algorithms were known for any value k > 3, except in the single-source setting. We show an O ( k log 3/2 r )-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. We complement these upper bounds by proving that VC-kRC is hard to approximate to within a factor of k ϵ for some fixed ϵ > 0. We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We give a simple bi-criteria approximation algorithm for this case, and show evidence that even this restricted version of the problem may be hard to approximate. For example, we prove that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige’s Random κ-AND assumption.

In the Node-Disjoint Paths (NDP) problem, the input is an undirected n-vertex graph G, and a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of vertices called demand pairs. The goal is to route the largest possible number of the demand pairs (s_i,t_i), by selecting a path connecting each such pair, so that the resulting paths are node-disjoint. NDP is one of the most basic and extensively studied routing problems. Unfortunately, its approximability is far from being well-understood: the best current upper bound of O(sqrt(n)) is achieved via a simple greedy algorithm, while the best current lower bound on its approximability is Omega(log^{1/2-\delta}(n)) for any constant delta. Even for seemingly simpler special cases, such as planar graphs, and even grid graphs, no better approximation algorithms are currently known. A major reason for this impasse is that the standard technique for designing approximation algorithms for routing problems is LP-rounding of the standard multicommodity flow relaxation of the problem, whose integrality gap for NDP is Omega(sqrt(n)) even on grid graphs. Our main result is an O(n^{1/4} * log(n))-approximation algorithm for NDP on grids. We distinguish between demand pairs with both vertices close to the grid boundary, and pairs where at least one of the two vertices is far from the grid boundary. Our algorithm shows that when all demand pairs are of the latter type, the integrality gap of the multicommodity flow LP-relaxation is at most O(n^{1/4} * log(n)), and we deal with demand pairs of the former type by other methods. We complement our upper bounds by proving that NDP is APX-hard on grid graphs.

The Flat Wall Theorem of Robertson and Seymour states that there is some function f, such that for all integers w,t > 1, every graph G containing a wall of size f(w, t), must contain either (i) a Kt-minor; or (ii) a small subset A ⊂ V(G) of vertices, and a flat wall of size w in G \ A. Kawarabayashi, Thomas and Wollan recently showed a self-contained proof of this theorem with the following two sets of parameters: (1) f(w,t) = Θ(t2 +w)) with |A| = O(t24), and (2) f(w,t) = w2Θ(t24)with |A| ≤ t – 5. The latter result gives the best possible bound on |A|. In this paper we improve their bounds to f(w,t) = Θ(t(t + w)) with |A| ≤ t – 5. For the special case where the maximum vertex degree in G is bounded by D, we show that, if G contains a wall of size Ω(Dt(t + w)), then either G contains a Kt-minor, or there is a flat wall of size w in G. This setting naturally arises in algorithms for the Edge-Disjoint Paths problem, with D ≤ 4. Like the proof of Kawarabayashi et al., our proof is self-contained, except for using a well-known theorem on routing pairs of disjoint paths. We also provide efficient algorithms that return either a model of the Kt-minor, or a vertex set A and a flat wall of size w in G \ A.

We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function f:Z+→ Z+, such that for any integer g> 0, any graph of treewidth at least f(g), contains the (g x g)-grid as a minor. Until recently, the best known upper bounds on f were super-exponential in g. A recent work of Chekuri and Chuzhoy provided the first polynomial bound, by showing that treewidth f(g)=O(g98 poly log g) is sufficient to ensure the existence of the (g x g)-grid minor in any graph. In this paper we provide a much simpler proof of the Excluded Grid Theorem, achieving a bound of $f(g)=O(g^{36} poly log g)$. Our proof is self-contained, except for using prior work to reduce the maximum vertex degree of the input graph to a constant.

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.

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.

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M = {(s1, t1),..., (sk, tk)} of demand pairs and an integer c. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c. When the maximum allowed congestion is c = 1, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an O(√n)-approximation, by rounding the standard multicommodity How relaxation of the problem. This matches the Ω(√n) lower bound on the integrality gap of this relaxation. We show an O(poly log k)-approximation algorithm for EDPwC with congestion c = 2, by rounding the same multi-commodity How relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of Ω̅(log n)1/(c+1)) for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was O̅(n3/7), and the best algorithm achieving a polylogarithmic approximation required congestion 14.

We study the k-route cut problem: given an undirected edge-weighted graph G = (V, E), a collection {(s1, t1), (s2, t2), …, (sr, tr)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E′ of edges to remove, such that the connectivity of every pair (si, ti) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k − 1) edge-disjoint paths connecting si to ti in G\E′, while in the vertex-connectivity version, VC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithms have been known for the special case where k ≤ 3, but no non-trivial approximation algorithms were known for any value k > 3, except in the single-source setting. We show an O(k log3/2 r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and VC-kRC, where the connectivity requirement k is violated by a constant factor. We complement these upper bounds by proving that VC-kRC is hard to approximate to within a factor of k∊ for some fixed ∊ > 0. We then turn to study a simpler version of VC-kRC, where only one source-sink pair is present. We give a simple bi-criteria approximation algorithm for this case, and show evidence that even this restricted version of the problem may be hard to approximate. For example, we prove that the single source-sink pair version of VC-kRC has no constant-factor approximation, assuming Feige's Random κ-AND assumption.

We study an integral counterpart of the classical Maximum Concurrent Flow problem, that we call Integral Concurrent Flow (ICF). In the basic version of this problem (basic-ICF), we are given an undirected n-vertex graph $G$ with edge capacities c(e), a subset T of vertices called terminals, and a demand D(t,t') for every pair (t,t') of the terminals. The goal is to find a maximum value λ, and a collection P of paths, such that every pair (t,t') of terminals is connected by ⌊ λ ⋅ D(t,t')⌋ paths in P, and the number of paths containing any edge e is at most c(e). We show an algorithm that achieves a poly log n-approximation for basic-ICF, while violating the edge capacities by only a constant factor. We complement this result by proving that no efficient algorithm can achieve a factor α-approximation with congestion c for any values α,c satisfying α ⋅ c=O(log log n/log log log n), unless NP ⊆ ZPTIME(npoly log n). We then turn to study the more general group version of the problem (group=ICF), in which we are given a collection (S1,T1),...,(Sk,Tk)} of pairs of vertex subsets, and for each 1 ≤ i ≤ k, a demand Di is specified. The goal is to find a maximum value λ and a collection P of paths, such that for each i, at least ⌊ λ ⋅ Di⌋ paths connect the vertices of Si to the vertices of Ti, while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O(n1/(22c+3))-approximation with congestion c for the problem, unless NP ⊆ DTIME(nO(log log n)). On the other hand, we show an efficient randomized algorithm that finds a poly log n-approximate solution with a constant congestion, if we are guaranteed that the optimal solution contains at least D ≥ k poly log n paths connecting every pair (Si,Ti).

Given an undirected graph G=(V,E) with edge capacities ce≥ 1 for e∈ E and a subset T of k vertices called terminals, we say that a graph H is a quality-q cut sparsifier for G iff T⊆ V(H), and for any partition (A,B) of T, the values of the minimum cuts separating A and B in graphs G and H are within a factor q from each other. We say that H is a quality-q flow sparsifier for G iff T⊆ V(H), and for any set D of demands over the terminals, the values of the minimum edge congestion incurred by fractionally routing the demands in D in graphs G and H are within a factor q from each other. So far vertex sparsifiers have been studied in a restricted setting where the sparsifier H is not allowed to contain any non-terminal vertices, that is V(H)=T. For this setting, efficient algorithms are known for constructing quality-O(log k/log log k) cut and flow vertex sparsifiers, as well as a lower bound of Ω(√log k) on the quality of any flow or cut sparsifier.

Given an undirected graph G=(V,E), a collection (s1,t1),...,(sk,tk) of k demand pairs, and an integer c, the goal in the Edge Disjoint Paths with Congestion problem is to connect maximum possible number of the demand pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed c. We show an efficient randomized algorithm that routes Ω(OPT/poly log k) demand pairs with congestion at most 14, where OPT is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The best previous algorithm that routed Ω(OPT/poly log n) pairs required congestion poly(log log n), and for the setting where the maximum allowed congestion is bounded by a constant c, the best previous algorithms could only guarantee the routing of OPT/nO(1/c) pairs.

Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with O(log2 n). (n + OPT) crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Planarization problem on graph G, then we can efficiently find a drawing of G with at most poly(d) · k · (k + OPT) crossings, where d is the maximum degree in G. This result implies an O(n · poly(d) · log3/2 n)-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.

We study the Minimum Crossing Number problem: given an n-vertex graph G, the goal is to find a drawing of G in the plane with minimum number of edge crossings. This is one of the central problems in topological graph theory, that has been studied extensively over the past three decades. The first non-trivial efficient algorithm for the problem, due to Leighton and Rao, achieved an O(n log4n)-approximation for bounded degree graphs. This algorithm has since been improved by poly-logarithmic factors, with the best current approximation ratio standing on O (n poly(d) log3/2n ) for graphs with maximum degree d. In contrast, only APX-hardness is known on the negative side.

We consider the following model for fire containment. We are given an undirected graph G = (V, E) with a source vertex s where the fire starts. At each time step, the firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease and its containment via vaccination. We focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T ⊆ V of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to the vertices of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an O(log* n)-approximation LP-rounding algorithm for RMFC on trees. We also show that an even stronger LP relaxation has an integrality gap of Ω(log* n) on trees. Finally, we consider RMFC on directed layered graphs, and show an O(log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation.

We consider the Max-Min Allocation problem: given a set A of m agents and a set I of n items, where agent A ¿ A has utility uA,i for item i ¿ I, our goal is to allocate items to agents so as to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an O¿(¿m)-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an algorithm that achieves an O¿(n¿)-approximation for any ¿ = ¿((log log n)/(log n)) in time nO(1/¿). In particular, we obtain poly-logarithmic approximation in quasipolynomial time, and for every constant ¿ > 0, we obtain an O¿(n¿)-approximation in polynomial time. An interesting technical aspect of our algorithm is that we use as a building block a linear program whose integrality gap is ¿(¿m). We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. As a corollary of our main result, we also show that for any constant ¿ > 0, an O(m¿)-approximation can be achieved in quasi-polynomial time. We also investigate the special case of the problem, where every item has non-zero utility for at most two agents. This problem is hard to approximate up to any factor better than 2. We give a factor 2-approximation algorithm.

In the Survivable Network Design problem (SNDP), we are given an undirected graph G(V, E) with costs on edges, along with a connectivity requirement r(u, v) for each pair u, v of vertices. The goal is to find a minimum-cost subset E* of edges, that satisfies the given set of pairwise connectivity requirements. In the edge-connectivity version we need to ensure that there are r(u, v) edge-disjoint paths for every pair u, v of vertices, while in the vertex-connectivity version the paths are required to be vertex-disjoint. The edge-connectivity version of SNDP is known to have a 2-approximation. However, no non-trivial approximation algorithm has been known so far for the vertex version of SNDP, except for special cases of the problem. We present an extremely simple algorithm to achieve an O(k3log |T|)-approximation for this problem, where k denotes the maximum connectivity requirement, and T is the set of vertices that participate in one or more pairs with non-zero connectivity requirements. We also give a simple proof of the recently discovered O(k3log |T|)-approximation algorithm for the single-source version of vertex-connectivity SNDP. Our results establish a natural connection between vertex-connectivity and a well-understood generalization of edge-connectivity, namely, element-connectivity, in that, any instance of vertex-connectivity can be expressed by a small number of instances of the element-connectivity problem.

We study the Maximum Independent Set of Rectangles (MISR) problem: given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles.MISR is a special case of the classical Maximum Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles.Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities.Since the problem is NP-hard, the main focus has been on the design of approximation algorithms.Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem.The main result of our paper is an O(log log n)-approximation algorithm for MISR.Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in the plane.We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by ddimensional hyper-rectangles.Our results for MISR imply an O((log n) d-2 log log n)-approximation algorithm for this problem, improving upon the best previously known O((log n) d-1 )-approximation.

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

In the survivable network design problem (SNDP) the goal is to find a minimum cost subset of edges that satisfies a given set of pairwise connectivity requirements among the vertices. This general network design framework has been studied extensively and is tied to the development of major algorithmic techniques. For the edge-connectivity version of the problem, a 2-approximation algorithm is known for arbitrary pairwise connectivity requirements. However, no non-trivial algorithms are known for its vertex connectivity counterpart. In fact, even highly restricted special cases of the vertex connectivity version remain poorly understood.We study the single-source k-vertex connectivity version of SNDP. We are given a graph G(V,E) with a subset T of terminals and a source vertex s, and the goal is to find a minimum cost subset of edges ensuring that every terminal is k-vertex connected to s. Our main result is an O(k log n)-approximation algorithm for this problem; this improves upon the recent 2O(k2)log4n-approximation. Our algorithm is based on an intuitive rerouting scheme. The analysis relies on a structural result that may be of independent interest: we show that any solution can be decomposed into a disjoint collection of multiple-legged spiders, which are then used to re-route flow from terminals to the source via other terminals.We also obtain the first non-trivial approximation algorithm for the vertex-cost version of the same problem, achieving an O(k7log2n)-approximation.

We study the survivable network design problem (SNDP) for vertex connectivity. Given a graph G(V,E) with costs on edges, the goal of SNDP is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. When all connectivity requirements are between a special vertex, called the source, and vertices in a subset T ⊆ V, called terminals, the problem is called the single-source SNDP. Our main result is a randomized kO(k2) log4n-approximation algorithm for single-source SNDP where k denotes the largest connectivity requirement for any source-terminal pair. In particular, we get a poly-logarithmic approximation for any constant k. Prior to our work, no non-trivial approximation guarantees were known for this problem for any k ≥ 3. We also show that SNDP is kΩ(1)-hard to approximate and provide an elementary construction that shows that the well-studied set-pair linear programming relaxation for this problem has an Ω(k1/3) integrality gap.

Consider the following classical network design problem: a set of terminals T = { t i } wishes to send traffic to a root r in an n -node graph G = ( V , E ). Each terminal t i sends d i units of traffic and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity u e and hence provisioning k × u e bandwidth on edge e incurs a cost of ⌈k⌉ times the cost of that edge. The objective is a minimum-cost feasible solution. This is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met. In this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than Ω(log log n ) unless NP ⊆ DTIME ( n O (log log log n ) ), where | V | = n . In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems.

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an NΩ(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have NO(log logN)-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor NO(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of NΩ(1/c) for c ranging from 1 to Θ((log n)/(log log n)).

We study the multicut and the sparsest cut problems in directed graphs. In the multicut problem, we are a given an n-vertex graphG along with k source-sink pairs, and the goal is to find the minimum cardinality subset of edges whose removal separates all source-sink pairs. The sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of deleted edges to the number of source-sink pairs that are separated by this deletion. The natural linear programming relaxation for multicut corresponds, by LP-duality, to the well-studied maximum (fractional) multicommodity flow problem, whilethe natural LP-relaxation for sparsest cut corresponds to maximum concurrent flow. Therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also the flow-cut gap: the maximum ratio, achievable for any graph,between the maximum flow value and the minimum cost solution for the corresponding cut problem. Starting with the celebrated max flow-mincut theorem of Ford and Fulkerson, flow-cut gaps have played acentral role in combinatorial optimization. For many NP-hard network optimization problems, the best known approximation guarantee corresponds to our understanding of the appropriate flow-cut gap.

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.

The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set L of labels and a weighted graph $G=(V,E)$. Additionally, a metric distance function on the labels is defined, and for each label and each vertex, an assignment cost is given. The goal is to find a minimum‐cost assignment of the vertices to the labels. The cost of the solution consists of two parts: the assignment costs of the vertices and the separation costs of the edges (where each edge pays its weight times the distance between the two labels to which its endpoints are assigned). Due to the simple structure and the variety of applications, the problem and its special cases (with various distance functions on the labels) have recently received much attention. Metric labeling is known to have a logarithmic approximation, and it has been an open question for some time whether a constant approximation exists. We refute this possibility and prove that no constant factor approximation algorithm exists for metric labeling unless P=NP. Moreover, we prove that the problem is $\Omega((\log |V|)^{1/2-\delta})$‐hard to approximate for any constant $\delta: 0<\delta<1/2$, unless NP has quasi‐polynomial time algorithms.

We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied.

We study the problem of minimum-distortion embedding of ultrametrics into the plane and higher dimensional spaces. Ultrametrics are a natural class of metrics that frequently occur in applications involving hierarchical clustering. Low-distortion embeddings of ultrametrics into the plane help visualizing complex structures they often represent. Given an ultrametric, a natural question is whether we can efficiently find an optimal-distortion embedding of this ultrametric into the plane, and if not, whether we can design an efficient algorithm that produces embeddings with near-optimal distortion. We show that the problem of finding minimum-distortion embedding of ultrametrics into the plane is NP-hard, and thus approximation algorithms are called for. Given an input ultrametric M, let c denote the minimum distortion achievable by any embedding of M into the plane. Our main result is a linear-time algorithm that produces an O(c 3)-distortion embedding. This result can be generalized to embedding ultrametrics into ℜ d, for any d ≥ 2, with distortion c O(d), where c is the minimum distortion achievable for embedding the input ultrametric into ℜ d. Additionally, we show that any ultrametric can be embedded into the plane with distortion O ( √ n), and in general, into ℜ d with distortion d O(1) n 1/d. Combining the two results together, we obtain an O(n 1/3)-approximation algorithm for the problem of minimumdistortion embedding of ultrametrics into the plane.

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

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs with minimum congestion on the network edges. The second problem is machine scheduling , where we are given a set of jobs, and for each job, there is a list of intervals on which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled such that no two jobs overlap in their execution on any machine. Both problems are known to be O (log n /log log n )-approximable via the randomized rounding technique of Raghavan and Thompson [1987]. However, until recently, only Max SNP hardness was known for each problem. We make progress in closing this gap by showing that both problems are Ω(log log n )-hard to approximate unless NP ⊆ DTIME( n O (log log log n ) ).

We consider the classical vertex cover and set cover problems with hard capacity constraints. This means that a set (vertex) can cover only a limited number of its elements (adjacent edges), and the number of available copies of each set (vertex) is bounded. This is a natural generalization of the classical problems which also captures resource limitations in practical scenarios. We obtain the following results. For the unweighted vertex cover problem with hard capacities we give a 3‐approximation algorithm that is based on randomized rounding with alterations. We prove that the weighted version is at least as hard as the set cover problem, yielding an interesting separation between the approximability of weighted and unweighted versions of a “natural” graph problem. A logarithmic approximation factor for both the set cover and the weighted vertex cover problem with hard capacities follows from the work of Wolsey [Combinatorica, 2 (1982), pp. 385–393] on submodular set cover. We provide here a simple and intuitive proof for this bound.

In the edge-disjoint paths problem with congestion (EDPwC), we are given a graph with n nodes, a set of terminal pairs and an integer c. The objective is to route as many terminal pairs as possible, subject to the constraint that at most c demands can be routed through any edge in the graph. When c = 1, the problem is simply referred to as the edge-disjoint paths (EDP) problem. In this paper, we study the hardness of EDPwC in undirected graphs. We obtain an improved hardness result for EDP, and also show the first polylogarithmic integrality gaps and hardness of approximation results for EDPwC. Specifically, we prove that EDP is (log/sup 1/2 - /spl epsiv// n)-hard to approximate for any constant /spl epsiv/ > 0, unless NP /spl sube/ ZPTIME(n/sup polylog n/). We also show that for any congestion c = o(log log n/log log log n), there is no (log/sup (1-/spl epsiv/)/(c+1)/ n) approximation algorithm for EDPwC, unless NP /spl sube/ ZPTIME(n/sup polylog n/). For larger congestion, where c /spl les/ /spl eta/ log log n/log log log n for some constant /spl eta/, we obtain superconstant inapproximability ratios. All of our hardness results can be converted into integrality gaps for the multicommodity flow relaxation. We also present a separate elementary direct proof of this integrality gap result. Finally, we note that similar results can be obtained for the all-or-nothing flow (ANF) problem, a relaxation of EDP, in which the flow unit routed between the source-sink pairs does not have follow a single path, so the resulting flow is not necessarily integral. Using standard transformations, our results also extend to the node-disjoint versions of these problems as well as to the directed setting.

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science.Most of the known embedding results are "absolute",that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c. This is beneficial if one can guarantee low distortion for all metrics Y in C. However, in any situations, the worst-case distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n - point star or an n -point cycle) are embeddable into X only with distortion linear in n. Nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications.A solution to this issue is to consider "relative" (or "approximation") embedding problems, where the goal is to design an (a-approxiation) algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion a *cY (X), where cY (X)is the best possible distortion of an embedding of X into Y.In this paper we show algorithms and hardness results for relative embedding problems.In particular we give: •an algorith that, given a general metric M, finds an embedding with distortion O (Δ3⁄4 poly(c line (M))), where Δ is the spread of M•an algorithm that,given a weighted tree etric M, finds an embedding with distortion poly(c line (M)) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in n,even for weighted tree metrics with spread Δ=n O (1).

In the ASYMMETRIC k -CENTER problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point from its center is as small as possible.We show that the ASYMMETRIC k -CENTER problem is hard to approximate up to a factor of log * n − O (1) unless NP ⊆ DTIME ( n log log n ). Since an O (log * n )-approximation algorithm is known for this problem, this resolves the asymptotic approximability of ASYMMETRIC k -CENTER. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric (symmetric) k -Center problem with costs.

The problem of scheduling jobs with interval constraints is a well-studied classical scheduling problem. The input to the problem is a collection of n jobs where each job has a set of intervals on which it can be scheduled. The goal is to minimize the total number of machines needed to schedule all jobs subject to these interval constraints. In the continuous version, the allowed intervals associated with a job form a continuous time segment, described by a release date and a deadline. In the discrete version of the problem, the set of allowed intervals for a job is given explicitly. So far, only an O(log n/( log log n))-approximation is known for either version of the problem, obtained by a randomized rounding of a natural linear programming relaxation of the problem. In fact, we show here that this analysis is tight for both versions of the problem by providing a matching lower bound on the integrality gap of the linear program. Moreover, even when all jobs can be scheduled on a single machine, the discrete case has recently been shown to be /spl Omega/(log log n)-hard to approximate. In this paper, we provide improved approximation factors for the number of machines needed to schedule all jobs in the continuous version of the problem. Our main result is an O(1)-approximation algorithm when the optimal number of machines needed is bounded by a fixed constant. Thus, our results separate the approximability of the continuous and the discrete cases of the problem. For general instances, we strengthen the natural linear programming relaxation in a recursive manner by forbidding certain configurations which cannot arise in an integral feasible solution. This yields an O(OPT)-approximation, where OPT denotes the number of machines needed by an optimal solution. Combined with earlier results, our work implies an O(/spl radic/log n/(log log n))-approximation for any value of OPT.

The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set of labels and a weighted graph. Additionally, a metric distance function on the labels is defined, and for each label and each vertex, an assignment cost is given. The goal is to find a minimum-cost assignment of the vertices to the labels. The cost of the solution consists of two parts: the assignment costs of the vertices and the separation costs of the edges (each edge pays its weight times the distance between the two labels to which its endpoints are assigned). Due to the simple structure and variety of the applications, the problem and its special cases (with various distance functions on the labels) have recently received much attention. Metric labeling has a known logarithmic approximation, and it has been an open question for several years whether a constant approximation exists. We refute this possibility and show that no constant approximation can be obtained for the problem unless P=NP, and we also show that the problem is /spl Omega/(/spl radic/logn)-hard to approximate, unless NP has quasi-polynomial time algorithms.

In the Asymmetric k-Center problem, the input is an integer k and a complete digraph over n points together with a distance function obeying the directed triangle inequality. The goal is to choose a set of k points to serve as centers and to assign all the points to the centers, so that the maximum distance of any point to its center is as small as possible. We show that the Asymmetric k-Center problem is hard to approximate up to a factor of log* n - Θ(1) unless NP ⊆ DTIME(nlog log n). Since an O(log* n)-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially relate to the known approximation classes. We also resolve the approximability threshold of the metric k-Center problem with costs.

We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. We are given a directed capacitated graph and a set of source-sink pairs. The goal is to route all pairs with minimum congestion on the network edges. A special well-studied case of this problem is the edge-disjoint paths problem, where all edges have unit capacities. The second problem is discrete machine scheduling, where we are given a set of jobs, and for each job a list of intervals in which it can be scheduled. The goal is to find the smallest number of machines on which all jobs can be scheduled, such that no two jobs assigned to the same machine overlap. Both problems are known to be O(log n/log log n)-approximable via the randomized rounding technique of Raghavan and Thompson. However, until recently, only a Max SNP hardness was known for each problem. We make some progress in closing this gap by showing that both problem are Ω(log log n)-hard to approximate unless NP ⊆ DTIME(nO(log log log n)). Our hardness proof for congestion minimization holds even for the special case of the edge-disjoint paths problem.

We consider the classical vertex cover and set cover problems with the addition of hard capacity constraints. This means that a set (vertex) can only cover a limited number of its elements (adjacent edges) and the number of available copies of each set (vertex) is bounded. This is a natural generalization of the classical problems that also captures resource limitations in practical scenarios. We obtain the following results. For the unweighted vertex cover problem with hard capacities we give a 3-approximation algorithm which is based on randomized rounding with alterations. We prove that the weighted version is at least as hard as the set cover problem. This is an interesting separation between the approximability of weighted and unweighted versions of a "natural" graph problem. A logarithmic approximation factor for both the set cover and the weighted vertex cover problem with hard capacities follows from the work of Wolsey (1982) on submodular set cover. We provide in this paper a simple and intuitive proof for this bound.

The authors consider the job interval selection problem (JISP), a simple scheduling model with a rich history and numerous applications. Special cases of this problem include the so-called real-time scheduling problem (also known as the throughput maximization problem) in single and multiple machine environments. In these special cases we have to maximize the number of jobs scheduled between their release date and deadline (preemption is not allowed). Even the single machine case is NP-hard. The unrelated machines case, as well as other special cases of JISP, are MAX SNP-hard. A simple greedy algorithm gives a 2-approximation for JISP. Despite many efforts, this was the best approximation guarantee known, even for throughput maximization on a single machine. The authors break this barrier and show an approximation guarantee of less than 1.582 for arbitrary instances of JISP. For some special cases, we show better results. Our methods can be used to give improved bounds for some related resource allocation problems that were considered recently in the literature.