Almost-Tight Hardness of Directed Congestion Minimization

Given a set of demands in a directed graph, the directed congestion minimization problem is to route every demand with the objective of minimizing the heaviest load over all edges. We show that for any constant epsilon > 0, there is no Omega(log(1-epsilon) M)-approximation algorithm on networks of size M unless NP subset of ZPTIME(n(polylog) (n)). This bound is almost tight given the O(log M/log log M)-approximation via randomized rounding due to Raghavan and Thompson.