All types (
22 )
agt (
3 )
approximation (
5 )
Conference (
15 )
Journal (
10 )
network (
10 )
Preprint (
3 )
probability (
6 )

Sort by year:

We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible.

Iterative rounding became the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very hard to adapt to settings where an edge can be part of a super-constant number of constraints. We consider a natural constrained spanning tree problem of this type, namely where upper bounds are imposed on a family of cuts forming a chain. Our approach reduces the problem to a family of independent matroid intersection problems, leading to a spanning tree that violates each constraint by a factor of at most 9.

We also present strong hardness results: among other implications, these are the first to show, in the setting of a basic constrained spanning tree problem, a qualitative difference between what can be achieved when allowing multiplicative as opposed to additive constraint violations.

We present a new strongly polynomial algorithm for generalized flow maximization. The first strongly polynomial algorithm for this problem was given in [Végh 2016]; our new algorithm is much simpler, and much faster. The complexity bound $O((m+n\log n)mn\log (n^2/m))$ improves on the previous estimate in [ Végh 2016] by almost a factor $O(n^2)$. Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.

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.

Robust network design refers to a class of optimization problems that occur when designing networks to efficiently handle variable demands. The notion of “hierarchical hubbing” was introduced (in the narrow context of a specific robust network design question), by Olver and Shepherd [2010]. Hierarchical hubbing allows for routings with a multiplicity of “hubs” which are connected to the terminals and to each other in a treelike fashion. Recently, Fréchette et al. [2013] explored this notion much more generally, focusing on its applicability to an extension of the well-studied hose model that allows for upper bounds on individual point-to-point demands. In this paper, we consider hierarchical hubbing in the context of a previously studied (and extremely natural) generalization of the hose model, and prove that the optimal hierarchical hubbing solution can be found efficiently. This result is relevant to a recently proposed generalization of the “VPN Conjecture”.

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

We consider the following network design problem. We are given an undirected graph $G=(V,E)$ with edges costs $c(e)$ and a set of terminal nodes $W$. A *hose* demand matrix for $W$ is any symmetric matrix $[D_{ij}]$ such that for each $i$, $\sum_{j \neq i} D_{ij} \leq 1$. We must compute the minimum cost edge capacities that are able to support the oblivious routing of every hose matrix in the network. An *oblivious routing* template, in this context, is a simple path $P_{ij}$ for each pair $i,j \in W$. Given such a template, if we are to route a demand matrix $D$, then for each $i,j$ we send $D_{ij}$ units of flow along each $P_{ij}$. Fingerhut et al. (1997) and Gupta et al. (2001) obtained a $2$-approximation for this problem, using a solution template in the form of a tree. It has been widely asked and subsequently conjectured that this solution actually results in the optimal capacity for the single path VPN design problem; this has become known as the *VPN conjecture*.

The conjecture has previously been proven for some restricted classes of graphs (Hurkens et al. 2005, Grandoni et al. 2007, Fiorini et al. 2007). Our main theorem establishes that this conjecture is true in general graphs. This proves that the single path VPN problem is solvable in polynomial time. We also show that the multipath version of the conjecture is false.

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap.

We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem – one that heavily exploits methods and results from the theory of matroids and submodular functions – which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap.

Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs.

For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.

Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare *oblivious* routing, where the routing between each terminal pair must be fixed in advance, to *dynamic* routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of $\Omega(\log{n})$ more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in Chekuri (2007), and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns (Chekuri et al. 2007).