Julia Chuzhoy, Sanjeev Khanna

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

Venkatesan Guruswami, Kunal Talwar

We prove a strong inapproximability result for routing on directed

graphs with low congestion. Given as input a directed graph on $N$

vertices and a set of source-destination pairs that can be connected

via edge-disjoint paths, we prove that it is hard, assuming NP

doesn't have $n^{O(\log\log n)}$ time randomized ...
more >>>