Logarithmic Hardness of the Directed Congestion Minimization Problem

We show that for any constant $ve>0$, there is no $Omega (log^{1-ve}M)$-approximation algorithm for the directed congestion minimization problem on networks of size $M$ unless $NPsubseteq ZPTIME(n^{polylog~n})$. This bound is almost tight given the $O(log M/loglog M)$-approximation via randomized rounding due to Raghavan and Thompson.