An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

A congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of flow demands in a network. A congestion approximator is hierarchical if it consists of a laminar family of cuts in the graph. There is a tradeoff between the running time for computing a congestion approximator and its approximation quality. Currently, for an n-node graph there exists a polynomial time algorithm that achieves a O (^1. 5n n) approximation and a near-linear time algorithm that achieves w. h. p. a O (⁴ n) approximation. In this paper we give the first near-linear time algorithm, that achieves w. h. p. a O (² n n) approximation, using an hierarchical congestion approximator with O (n n) cuts. Based on a reduction from oblivious routing, we also present a lower bound of Ω (n) for the approximation quality of hierarchical congestion approximators. Our algorithm can also be implemented in the parallel setting achieving the same approximation quality, polylogarithmic span and near-linear work. This improves upon the best prior parallel algorithm, which has a O (⁹n) approximation. Crucial for achieving a near linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and give an improved sparsest cut oracle for general vertex weights.