Flexible network design deals with building a network that guarantees some connectivity requirements between its vertices, even when some of its elements (like vertices or edges) fail. In particular, the set of edges (resp. vertices) of a given graph are here partitioned into safe and unsafe. The goal is to identify a minimum size subgraph that is 2-edge-connected (resp. 2-vertex-connected), and stay so whenever any of the unsafe elements gets removed. In this paper, we provide improved approximation algorithms for flexible network design problems, considering both edge-connectivity and vertex-connectivity, as well as connectivity values higher than 2. For the vertex-connectivity variant, in particular, our algorithm is the first with approximation factor strictly better than 2.

This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems: Steiner Tree and Node-Tree Augmentation. We will show how a wiser choice of witness trees leads to an improved approximation for Node-Tree Augmentation, and for Steiner Tree in special classes of graphs.

The combinatorial diameter of a polytope $P$ is the maximum value of a shortest path between two vertices of $P$, where the path uses the edges of $P$ only. In contrast to the combinatorial diameter, the circuit diameter of $P$ is defined as the maximum value of a shortest path between two vertices of $P$, where the path uses potential edge directions of $P$, i.e., all edge directions that can arise by translating some of the facets of $P$. In this paper, we study the circuit diameter of polytopes corresponding to classical combinatorial optimization problems, such as the matching polytope, the Traveling Salesman polytope, and the fractional stable set polytope.

We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [D. Burton and Ph.L. Toint, 1992; W. Ben-Ameur and E. Gourdin, 2004; A. Bley, 2007], which finds applications in shortest-path routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum l_infty norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized. Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P!=NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including l_p-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

The (combinatorial) diameter of a polytope P ⊆ ℝdis the maximum value of a shortest path between a pair of vertices on the 1-skeleton of P, that is the graph where the nodes are given by the 0-dimensional faces of P, and the edges are given the 1-dimensional faces of P. The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In particular, [Frieze and Teng, 1994] showed that computing the diameter of a polytope is (weakly) NP-hard. In this paper, we show that the problem of computing the diameter is strongly NP-hard even for a polytope with a very simple structure: namely, the fractional matching polytope. We also show that computing a pair of vertices at maximum shortest path distance on the 1-skeleton of this polytope is an APX-hard problem. We prove these results by giving an exact characterization of the diameter of the fractional matching polytope, that is of independent interest.

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree G = (V, E) with n = |V| nodes, an additional set of edges L called links and a cost vector . The goal is to choose a minimum cost subset S ⊆ L such that G = (V, E ∪ S) is 2-edgeconnected. In the unweighted case, that is, when we have cℓ = 1 for all ℓ ∊ L, the problem is called the tree augmentation problem (TAP). Both problems are known to be APX-hard, and the best known approximation factors are 2 for WTAP by (Frederickson and JáJá, ’81) and for TAP due to (Kortsarz and Nutov, TALG ’16). Adjashvili (SODA ’17) recently presented an ≈ 1.96418 + ε-approximation algorithm for WTAP for the case where all link costs are bounded by a constant. This is the first approximation with a better guarantee than 2 that does not require restrictions on the structure of the tree or the links. In this paper, we improve Adjiashvili's approximation to a + ε-approximation for WTAP under the bounded cost assumption. We achieve this by introducing a strong LP that combines {0, ½}-Chvátal-Gomory cuts for the standard LP for the problem with bundle constraints from Adjiashvili. We show that our LP can be solved efficiently and that it is exact for some instances that arise at the core of Adjiashvili's approach. This results in the improved performance guarantee of + ε, which is asymptotically on par with the result by Kortsarz and Nutov. Our result also is the best-known LP-relative approximation algorithm for TAP.

We study a generalization of the Steiner tree problem, where we are given a weighted network G together with a collection of k subsets of its vertices and a root r. We wish to construct a minimum cost network such that the network supports one unit of flow to the root from every node in a subset simultaneously. The network constructed does not need to support flows from all the subsets simultaneously. We settle an open question regarding the complexity of this problem for k=2, and give a 3/2-approximation algorithm that improves over a (trivial) known 2-approximation. Furthermore, we prove some structural results that prevent many well-known techniques from doing better than the known O(log n)-approximation. Despite these obstacles, we conjecture that this problem should have an O(1)-approximation. We also give an approximation result for a variant of the problem where the solution is required to be a path.

In a standard $f$-connectivity network design problem, we are given an undirected graph $G=(V,E)$, a cut-requirement function $f:2^V \rightarrow {\mathbb{N}}$, and non-negative costs $c(e)$ for all $e \in E$. We are then asked to find a minimum-cost vector $x \in {\mathbb{N}}^E$ such that $x(δ(S)) \geq f(S)$ for all $S \subseteq V$. We focus on the class of such problems where $f$ is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the $f$-connectivity problem with general proper functions $f$. Implementing Jain's algorithm, this yields a strongly polynomial time $(2+ε)$-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation).

In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403--417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices.

We study the k-route generalizations of various cut problems, the most general of which is k-route multicut (k-MC) problem, wherein we have r source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below k. The k-route extensions of multiway cut (k-MWC), and the minimum s-t cut problem (k-(s, t)-Cut), are similarly defined. We present various approximation and hardness results for k-MC, k-MWC, and k-(s,t)-Cut that improve the state-of-the-art for these problems in several cases. Our contributions are threefold. For k-route multiway cut, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. For k-route multicut, we design algorithms that improve upon the previous-best approximation factors by roughly an -factor, when k = 2, and for general k and unit costs and any fixed violation of the connectivity threshold k. The main technical innovation is the definition of a new, powerful region growing lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a different metric for each source-sink pair, and without incurring an O(log2 r) blow-up in the cost that is inherent in some previous applications of region growing to k-route cuts. We obtain the same benefits as [15] do in their divide-and-conquer algorithms, and thereby obtain an O(ln r ln ln r)-approximation to the cost. We also obtain some extensions to k-route node-multicut problems. We complement these results by showing that the k-route s-t cut problem is at least as hard to approximate as the densest-k-subgraph (DkS) problem on uniform hypergraphs. In particular, this implies that one cannot avoid a poly(k)-factor if one seeks a unicriterion approximation, without improving the state-of-the-art for DkS on graphs, and proving the existence of a family of one-way functions. Previously, only NP-hardness of k-(s; t)-Cut was known.

The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well. We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known. In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

In the node-weighted prize-collecting Steiner tree problem (NW-PCST) we are given an undirected graph G = (V, E), non-negative costs c(u) and penalties π(u) for each u ∈ V . The goal is to find a tree T that minimizes the total cost of the vertices spanned by T plus the total penalty of vertices not in T. This problem is well-known to be set-cover hard to approximate. Moss and Rabani (STOC'01) presented a primal-dual Lagrangean-multiplier-preserving O(ln |V |)-approximation algorithm for this problem. We show a serious problem with the algorithm, and present a new, fundamentally different primal-dual method achieving the same performance guarantee. Our algorithm introduces several novel features to the primal-dual method that may be of independent interest.

The Steiner tree problem is one of the most fundamental NP -hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999]. In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) + ε < 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence. As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.

Some of the routing protocols used in telecommunication networks route traffic on a shortest path tree according to configurable integral link weights. One crucial issue for network operators is finding a weight function that ensures a stable routing: when some link fails, traffic whose path does not use that link should not be rerouted. In this paper we improve on several previously best results for finding small stable weights. As a conceptual contribution, we draw a connection between the stable weights problem and the seemingly unrelated unique-max coloring problem. In unique-max coloring, one is given a set of points and a family of subsets of those points called regions. The task is to assign to each region a color represented as an integer such that, for every point, one region containing it has a color strictly larger than the color of any other region containing this point. In our setting, points and regions become edges and paths of the shortest path tree, respectively, and based on this connection, we provide stable weight functions with a maximum weight of $O(n \log n)$ in the case of single link failure, where $n$ is the number of vertices in the network. Furthermore, if the root of the shortest path tree is known, we present an algorithm for determining stable weights bounded by $4n$, which is optimal up to constant factors. For the case of an arbitrary number of failures, we show how stable weights bounded by $3^n n$ can be obtained. All the results improve on the previously best known bounds.

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.

Only recently Goyal, Olver, and Shepherd [Proc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms, 24 (1997), pp. 287–309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry.