logarithmic hardness of the directed congestion minimization problem
We show that for any constant ? > 0, there is no ?(log 1-? M)-approximation algorithm for the directed congestion minimization problem on networks of size M unless NP ? 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.
congestion minimization hardness of approximation directed graphs