hardness of the undirected congestion minimization problem
We show that there is no (log log M ) 1-? approximation for the undirected congestion minimization problem unless NP ? ZPTIME ( n polylogn ), where M is the size of the graph and ? is any positive constant.
congestion minimization undirected graphs hardness of approximation