Papers

The well-known grid example of Garg-Vazriani-Yannakakis shows that the integrality gap for the natural LP formulation of the undirected maximum edge-disjoint paths problem is $\Omega(\sqrt{n})$ even in planar graphs. Chekuri, Khanna and Shepherd established that a constant factor gap hols in planar graphs if edge-congestion $4$ is allowed. It is natural to ask for which classes of graphs does such a constant-factor constant-congestion hold. Its easy to deduce that for given constant bounds on the approximation and congestion, the class of ``nice'' graphs is minor-closed. Is the converse true? Does every minor-closed class exhibit such a constant factor/congestion bound relative to the LP formulation? One stumbling block for this problem is the fact that such bounds were not known for bounded treewidth graphs. In this paper we give a polytime algorithm which takes a fractional routing solution in a bounded treewidth graph and is able to integrally route (with congestion 1!) a constant fraction of the LP solution's value. This is the only such congestion 1 result known (apart from trees). The arguments also work for $k$-sums of graphs in some family, as long as the graph family has a constant factor/congestion bound. We use this to obtain such bounds hold for the class of $k$-sums of bounded genus graphs.

We resolve the longstanding gap on the competitive ratio for d-dimensional online vector bin packing (VBP). The best lower bound was 2 compared with the best upper bound of d+.7. When the bin sizes B are 1, we use a lower bound for online colouring (Halldorosson and Szegedy, 1992) and an idea of ${\displaystyle }$preparing'' for future adjacencies to easily get a ${\displaystyle \sqrt{d}}$ lower bound. This is boosted to ${\displaystyle d^{1-eps}}$ using an idea from (Dean-Goemans-Vondrak, 2005) in their work on approximability of stochastic packing integer programs. The lower bounds are more intricate in the cases when ${\displaystyle B\ge 2}$. We give almost matching upper bounds of ${\displaystyle O\left(B{d}^{1/B}logn\right)}$ in that case.

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed-demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices, in order to see which traffic models are more shortest path-like as opposed to hub-like. In order to address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design ($\rnd$) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical $\rnd$ problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands. This study also reveals conditions under which multi-hub routing gives improvements over single-hub and shortest-path routings.

We want to build a network that can transport any demand matrix ${\displaystyle \left(D_{ij}\right)}$ where ${\displaystyle \sum _j{D}_{ij}\le b_i}$. The ${\displaystyle b_i}$'s are called marginals - they simply indicate that the total demand (traffic) involving node ${\displaystyle i}$ is at most ${\displaystyle b_i}$. The class of all such matrices are called the hose matrices. We dont know or care who ${\displaystyle i}$ will actually communicate with. In addition, we must route traffic "obliviously", which means that routing of traffic between nodes ${\displaystyle i}$ and ${\displaystyle j}$ does not depend on what other traffic there is in the network. In other words, our routing cannot adapt to congestion in the network: we must prespecify how any pair communicates regardless of which hose demand matrix we are given. Our goal is to find an oblivious routing such that the total capacity needed on the edges of the network is minimized. This is called the Virtual Private Network (VPN) problem. Fingerhut-Suri-Turner and Gupta-Kleinberg-Kumar-Rastogi-Yener showed that there is always a tree network whose total cost is within a factor of 2 of the minimum cost VPN. It was widely speculated and conjectured in Italiano-Leonardi-Oriolo, that there is always an optimal VPN which is a tree. We show this is true using pyramidal routing, a concept recently introduced by Grandoni-Kaibel-Oriolo-Skutella to attack the VPN problem.

The maximum edge-disjoint path problem (EDP) consist of a supply graph and some terminal pairs ${\displaystyle s_i,t_i}$ for ${\displaystyle i=1,2...,k}$. The goal is to find a maximum subset of the pairs that can be simultaneously satisfied by disjoint paths in the supply graph. Guruswami et al. (see below) showed that in directed graphs the maximum edge-disjoint path problem (EDP) is hard to polytime approximate to better than a factor of ${\displaystyle m^{.5-\epsilon }}$ (where m is the number arcs and any ${\displaystyle \epsilon >0}$). However similar hardness results were not known for the undirected version (it was only known to be hard to constant approximate). This paper studies a relaxation of EDP in undirected graphs, the all-or-nothing multicommodity flow problem, where one is only asked to find a subset of the pairs for which there is a flow satisfying their demands. The main result is that the integrality gap for this relaxation is at most a polylogarithmic factor (thus exponentially better than for directed graphs). Recently an almost matching polylogarithmic lower bound was found by Andrews and Zhang.