On the approximability of some network design problems

ABSTRACT

Consider the following classical network design problem: a set of terminals T = {t_i} wishes to send traffic to a root r in an n-node graph G = (V, E). Each terminal t_i sends d_i units of traffic and enough bandwidth has to be allocated on the edges to permit this. However, bandwidth on an edge e can only be allocated in integral multiples of some base capacity u_e and hence provisioning k × u_e bandwidth on edge e incurs a cost of ⌈k⌉ times the cost of that edge. The objective is a minimum-cost feasible solution.

This is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met.

In this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than Ω(log log n) unless NP ⊆ DTIME (n^{O(log log log n)}), where |V| = n. In particular, we show that this inapproximability threshold holds for (i) the Priority-Steiner Tree problem, (ii) the (single-sink) Cost-Distance problem, and (iii) the single-sink version of an even more fundamental problem, Fixed Charge Network Flow. Our results provide a further breakthrough in the understanding of the level of complexity of network design problems. These are the first nonconstant hardness results known for all these problems.

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: Andrews, M., and Zhang, L. 2002. Approximation algorithms for access network design. Algorithmica 34, 2, 197--215.
• 3: 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]
• 4: B. Awerbuch , Y. Azar, Buy-at-bulk network design, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.542, October 19-22, 1997
• 5: Robert D. Carr , Lisa K. Fleischer , Vitus J. Leung , Cynthia A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.106-115, January 09-11, 2000, San Francisco, California, United States
• 6: Moses Charikar , Joseph (Seffi) Naor , Baruch Schieber, Resource optimization in QoS multicast routing of real-time multimedia, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.340-348, April 2004 [doi>10.1109/TNET.2004.826288]
• 7: Chandra Chekuri , Sanjeev Khanna , Joseph (Seffi) Naor, A deterministic algorithm for the cost-distance problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.232-233, January 07-09, 2001, Washington, D.C., United States
• 8: Andrea E. F. Clementi, Improved non-approximability results for minimum vertex cover with density constraints, Theoretical Computer Science, v.225 n.1-2, p.113-128, Aug. 28, 1999 [doi>10.1016/S0304-3975(97)00226-0]
• 9: Current, J. R., Revelle, C. S., and Cohon, J. L. 1986. The hierarchical network design problem. European J. Oper. Resear. 27, 57--66.
• 10: Duin, C., and Volgenant, T. 1991. The multi-weighted Steiner tree problem. Ann. Oper. Resear. 33, 1-4, 451--469. Topological network design (Copenhagen, 1989).
• 11: Guy Even , Guy Kortsarz , Wolfgang Slany, On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.318-327, July 03-05, 2002
• 12: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 13: Naveen Garg , Rohit Khandekar , Goran Konjevod , R. Ravi , F. S. Salman , Amitabh Sinha, On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.170-184, June 13-15, 2001
• 14: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Journal of Algorithms, v.31 n.1, p.228-248, April 1999 [doi>10.1006/jagm.1998.0993]
• 16: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 17: Sudipto Guha , Adam Meyerson , Kamesh Munagala, A constant factor approximation for the single sink edge installation problems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.383-388, July 2001, Hersonissos, Greece [doi>10.1145/380752.380827]
• 18: Gunluk, O. 1999. A branch-and-cut algorithm for capacitated network design problems. Math. Program. 86, 17--39.
• 19: Anupam Gupta , Amit Kumar , Martin Pál , Tim Roughgarden, Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.606, October 11-14, 2003
• 20: Anupam Gupta , Amit Kumar , Tim Roughgarden, Simpler and better approximation algorithms for network design, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780597]
• 21: Eran Halperin , Robert Krauthgamer, Polylogarithmic inapproximability, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780628]
• 22: Jain, K. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 1, 39--60.
• 23: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 24: Amit Kumar , Anupam Gupta , Tim Roughgarden, A Constant-Factor Approximation Algorithm for the Multicommodity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.333, November 16-19, 2002
• 25: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 26: Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
• 27: Maxemchuk, N. F. 1997. Video distribution on multicast networks. IEEE J. Select. Areas Comm. 15, 357--372.
• 28: Vardges Melkonian , Éva Tardos, Approximation Algorithms for a Directed Network Design Problem, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.345-360, June 09-11, 1999
• 29: Adam Meyerson, Online algorithms for network design, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007958]
• 30: A. Meyerson , K. Munagala , S. Plotkin, Cost-distance: two metric network design, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.624, November 12-14, 2000
• 31: Mirchandani, P. 1996. The multi-tier tree problem. INFORMS J. Comput. 8, 202--218.
• 32: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 33: Ortega, F., and Wolsey, L. A. 2003. A branch-and-cut algorithm for the single-commodity, uncapacitated, fixed-charge network flow problem. Networks 41, 3, 143--158.
• 34: Pirkul, H., Current, J., and Nagarajan, V. 1991. The hierarchical network design problem: a new formulation and solution procedures. Transport. Sci. 25, 175--182.
• 35: R. Ravi , F. S. Salman, Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design, Proceedings of the 7th Annual European Symposium on Algorithms, p.29-40, July 16-18, 1999
• 36: Ravi Ramamoorthi , Amitabh Sinha, Integrated Logistics: Approximation Algorithms Combining Facility Location and Network Design, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.212-229, May 27-29, 2002
• 37: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 38: F. S. Salman , J. Cheriyan , R. Ravi , S. Subramanian, Approximating the Single-Sink Link-Installation Problem in Network Design, SIAM Journal on Optimization, v.11 n.3, p.595-610, 2000 [doi>10.1137/S1052623497321432]
• 39: Chaitanya Swamy , Amit Kumar, Primal-Dual Algorithms for Connected Facility Location Problems, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.256-270, September 17-21, 2002
• 40: Kunal Talwar, The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.475-486, May 27-29, 2002
• 41: Turletti, T., and Bolot, J.-C. 1994. Issues with multicast video distribution in heterogeneous packet networks. In Proceedings of 6th International Workshop on Packet Video.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
Hardness of approximation, cost-distance, fixed charge network flow, network design, priority Steiner tree