Almost-tight hardness of directed congestion minimization

ABSTRACT

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.

REFERENCES

• 1: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 2: Matthew Andrews , Julia Chuzhoy , Lisa Zhang, Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.226-244, October 23-25, 2005 [doi>10.1109/SFCS.2005.41]
• 3: Andrews, M., and Zhang, L. 2005a. Bounds on fiber minimization in optical networks with fixed fiber capacity. In Proceedings of IEEE INFOCOM '05. IEEE Computer Society Press, Los Alamitos, CA.
• 4: Matthew Andrews , Lisa Zhang, Hardness of the undirected congestion minimization problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060633]
• 5: Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060632]
• 6: Andrews, M., and Zhang, L. 2006. Complexity of wavelength assignment in optical network optimization. In Proceedings of IEEE INFOCOM '06. IEEE Computer Society Press, Los Alamitos, CA.
• 7: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 8: Julia Chuzhoy , Venkatesan Guruswami , Sanjeev Khanna , Kunal Talwar, Hardness of routing with congestion in directed graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250816]
• 9: Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007364]
• 10: Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds. 85--103.
• 11: Tom Leighton , Satish Rao , Aravind Srinivasan, Multicommodity Flow and Circuit Switching, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.459, January 06-09, 1998 [doi>10.1109/HICSS.1998.649241]
• 12: Martens, M., and Skutella, M. 2004. Flows on few paths: Algorithms and lower bounds. In Proceedings of the 12th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3221. Springer-Verlag, New York, 520--531.
• 13: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 14: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Hardness of approximation, congestion minimization, undirected graphs