Almost-tight hardness of directed congestion minimization
Matthew Andrews, Lisa Zhang · Journal of the ACM · 2008
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 ε > 0, there is no Ω(log 1−ε M )-approximation algorithm 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.