Hardness of the undirected congestion minimization problem
Matthew Andrews, Lisa M. Zhang · 2005
We show that there is no (log log M)1-ε approximation for the undirected congestion minimization problem unless NP ⊆ ZPTIME(npolylogn), where M is the size of the graph and ε is any positive constant.