The single-source unsplittable flow problem asks to send flow in a digraph with capacities from a common source to different terminals with unrelated demands, each terminal being served through a single path. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. So far there are no non-trivial graph classes for which it is known to hold.

In the talk, we will see that a slight weakening of it (with at most twice as large violations) holds for planar graphs. This result is based on a connection to a highly structured discrepancy problem, whose repeated resolution allows us to successively reduce the number of paths used for each terminal, until we obtain an unsplittable flow.

This is joint work with Vera Traub and Rico Zenklusen.

Expander decompositions are one of the most ubiquitous and flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this paradigm to better work for problems with lengths, distances and costs. Roughly, an (h,s)-length phi-expander decomposition is a collection of length increases to a graph so that nodes within distance h can route flow over paths of length hs with congestion at most 1/phi.

This talk, will cover new close-to-linear-time algorithms for computing length-constrained expander decompositions in graphs with general lengths and capacities. These algorithms allow one to trade off off between the size of the decomposition and the length of routing paths: for any eps > 0 not too small, it computes in almost-linear-time an (h,s)-length phi-decomposition of size Hershkowitz where s = exp(poly(1/eps)). The key foundations of our algorithm are: (1) a simple yet powerful structural theorem which states that the union of a sequence of sparse length-constrained cuts is itself sparse and (2) new algorithms for computing sparse length-constrained flows.

Based on joint work with Zihan Tan and Bernhard Haeupler.

Computing k-edge-connected spanning subgraphs of minimum cost is a fundamental problem in combinatorial optimization. For k=1, this is exactly the minimum spanning tree problem. For general k this is known as the k-edge-connected spanning subgraph (k-ECSS) problem and is NP-Hard. A 2-approximation for this problem can be obtained by a variety of techniques such as Jain's iterative rounding, and obtaining a better-than-2 approximation for any k is a major open question.

In this work, we approach approximating k-ECSS from a resource augmentation perspective, inspired by resource augmentation results on other network design problems like bounded degree spanning trees. I will describe an algorithm that returns a k-ECSS solution of cost no greater than the cheapest (k+10)-ECSS. Equivalently, we can find a (k-10)-ECSS solution of cost no more than the cheapest k-ECSS. Thus, for large k, this presents a promising alternative to a 2-approximation: instead of losing a factor 2 in the cost, one can instead lose O(1) connectivity. As a byproduct of this result, we also obtain a 1+O(1/k) for the k-ECSM problem, a variant of k-ECSS in which one can select an edge multiple times at the same cost. This resolves a conjecture of Pritchard from 2011 and improves upon a recent work of Karlin, Klein, Oveis Gharan, and Zhang. We also give a matching lower bound of 1+Omega(1/k), showing that this is the best possible asymptotic ratio unless P=NP.

Based on joint work with D Ellis Hershkowitz and Rico Zenklusen.

In several standard network design problems, given an input graph with fixed edge costs and source/sink pairs of vertices, the goal is to find a low-cost subgraph satisfying some connectivity properties. We consider two-cost network design models, in which edges of the input graph have an associated length along with the fixed cost. One fundamental such problem is the multicommodity buy-at-bulk problem: given demand pairs si, ti with demand d(i), the goal is to route d(i) flow between si and ti while minimizing the sum of the fixed cost (total cost of edges used) and oruting cost (total length of flow paths). Chekuri et al. gave a polylogarithmic approximation via junction trees and posed the question of establishing an upper bound on the integrality gap of a natural LP relaxation.

In this talk, we will see that we can obtain a polylogarithmic upper bound on the integrality gap using recent results in hop-constrained oblivious routing. We demonstrate a connection between h-hop-constrained network design problems (in which each demand pair must be connected with a path of at most h edges) and obtain bi-criteria approximation algorithms for these problems as well.

This is joint work with Chandra Chekuri.