On network design problems: fixed cost flows and the covering steiner problem

ABSTRACT

Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying positive flow.We prove a hardness result for the Minimum Edge Cost Flow Problem (MECF). Using the one-round two-prover scenario, we prove that MECF does not admit a 2^{log1-ϵ n}-ratio approximation, for every constant ϵ > 0, unless NP ⊆ DTIME(n^polylogn).A restricted version of MECF, called Infinite Capacity MECF (ICF), is defined. The ICF problem is defined as follows: (i) all edges have infinite capacity, (ii) there are multiple sources and sinks, where flow can be delivered from every source to every sink, (iii) each source and sink has a supply amount and demand amount, respectively, and (iv) the required total flow is given as part of the input. The goal is to find a minimum edge-cost flow that meets the required total flow while obeying the demands of the sinks and the supplies of the sources. This problem naturally arises in practical scheduling applications, and is equivalent to the special case of single source MECF, with all edges not touching the source or the sink having infinite capacity.The directed ICF generalizes the Covering Steiner Problem in directed and undirected graphs. The undirected version of ICF generalizes several network design problems, such as: Steiner Tree Problem, k-MST, Point-to-point Connection Problem, and the generalized Steiner Tree Problem.An O(log x)-approximation algorithm for undirected ICF is presented. We also present a bi-criteria approximation algorithm for directed ICF. The algorithm for directed ICF finds a flow that delivers half the required flow at a cost that is at most O(n^ϵ/ϵ⁴) times bigger than the cost of an optimal flow. The running time of the algorithm is O(x^2/ϵ ċ n^1+1/ϵ), where x denotes the required total flow.Randomized approximation algorithms for the Covering Steiner Problem in directed and undirected graphs are presented. The algorithms are based on a randomized reduction to a problem called 1/2-Group Steiner. In undirected graphs, the approximation ratio matches the approximation ratio of Konjevod et al. [2002]. However, our algorithm is much simpler. In directed graphs, the algorithm is the first nontrivial approximation algorithm for the Covering Steiner Problem. Deterministic algorithms are obtained by derandomization.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 2: Kouji Arata , Satoru Iwata , Kazuhisa Makino , Satoru Fujishige, Locating Sources to Meet Flow Demands in Undirected Networks, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.300-313, July 05-07, 2000
• 3: Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: Avrim Blum , R. Ravi , Santosh Vempala, A constant-factor approximation algorithm for the k-MST problem, Journal of Computer and System Sciences, v.58 n.1, p.101-108, Feb. 1999 [doi>10.1006/jcss.1997.1542]
• 6: Moses Charikar , Chandra Chekuri, Approximation algorithms for directed Steiner problems, Journal of Algorithms, v.33 n.1, p.73-91, Oct. 1999 [doi>10.1006/jagm.1999.1042]
• 7: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 8: Fabián A. Chudak , Tim Roughgarden , David P. Williamson, Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.60-70, June 13-15, 2001
• 9: Teodor Gabriel Crainic , Antonio Frangioni , Bernard Gendron, Bundle-based relaxation methods for multicommodity capacitated fixed charge network design, Discrete Applied Mathematics, v.112 n.1-3, p.73-99, September 15, 2001 [doi>10.1016/S0166-218X(00)00310-3]
• 10: Di Gaspero, L., Gärtner, J., Kortsarz, G., Musliu, N., Schaerf, A., and Slany, W. 2003. The minimum shift design problem: Theory and practice. In Proceedings of the European Symposium on Algorithms (ESA), pp. 593--604.
• 11: Diestel, R. 2000. Graph theory, 2nd Ed. Springer-Verlag, New York, URL: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.
• 12: Equi, L., Gallo, G., Marziale, S., and Weintraub, A.1997. A combined transportation and scheduling problem. Europ. J. Oper. Res. 97, 1, 94--104.
• 13: Peter C. Fetterolf , G. Anandalingam, A Lagrangian relaxation technique for optimizing interconnection of local area networks, Operations Research, v.40 n.4, p.678-688, July-Aug. 1992 [doi>10.1287/opre.40.4.678]
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: N. Garg, A 3-approximation for the minimum tree spanning k vertices, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.302, October 14-16, 1996
• 16: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 17: Gendron, B., and Crainic, T. G.1996. Bounding procedures for multicommodity capacitated fixed charge network design problems. Publication CRT-96-06, Centre de recherche sur les transports, Université de Montréal, Montreal, Ont., Canada.
• 18: 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
• 19: Maud Göthe-Lundgren , Torbjörn Larsson, A set covering reformulation of the pure fixed charge transportation problem, Discrete Applied Mathematics, v.48 n.3, p.245-259, Feb. 15, 1994
• 20: Hochbaum, D. S., and Segev, A.1989. Analysis of a flow problem with fixed charges. Networks 19, 3, 291--312.
• 21: Holmberg, K., and Yuan, D.1997. A Lagrangean heuristic-based branch-and-bound approach for the capacitated network design problem. In Proceedings of the 4th Meeting of the Nordic Section of the Mathematical Programming Society (Arhus, Denmark, Aug. 16--18). Kim Allan Andersen ed., Univ. of Arhus, Department of Operations Research, Publications at the Departments of Mathematical Sciences. Working Papers 97-1, pp. 62--97.
• 22: Johnson, D. S. 1974. Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9, 256--278.
• 23: Kim, D., and Pardalos, P. M.1999. A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Oper. Res. Lett. 24, 4, 195--203.
• 24: Goran Konjevod , R. Ravi, An approximation algorithm for the covering Steiner problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.338-344, January 09-11, 2000, San Francisco, California, United States
• 25: Goran Konjevod , R. Ravi , Aravind Srinivasan, Approximation algorithms for the covering Steiner problem, Random Structures & Algorithms, v.20 n.3, p.465-482, May 2002 [doi>10.1002/rsa.10038]
• 26: Guy Kortsarz, On the Hardness of Approximation Spanners, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.135-146, July 18-19, 1998
• 27: Guy Kortsarz , David Peleg, Approximating the weight of shallow Steiner trees, Discrete Applied Mathematics, v.93 n.2-3, p.265-285, July 20, 1999 [doi>10.1016/S0166-218X(99)00111-0]
• 28: Krumke, S. O., Noltemeier, H., Schwarz, S., Wirth, H.-C., and Ravi, R.1998. Flow improvement and network flows with fixed costs. OR-98, Zürich.
• 29: Lau, H. C.1996. Combinatorial approaches for hard problems in manpower scheduling. J. Oper. Res. Soc. Japan 39, 1, 88--98.
• 30: Leiserson, C. E., and Saxe, J. B.1991. Retiming synchronous circuitry. Algorithmica 6, 1, 5--35.
• 31: Chung-Lun Li , S. Thomas McCormick , David Simchi-Levi, The point-to-point delivery and connection problems: complexity and algorithms, Discrete Applied Mathematics, v.36 n.3, p.267-292, May 28, 1992 [doi>10.1016/0166-218X(92)90258-C]
• 32: Magnanti, T. L., and Wong, R. T.1984. Network design and transportation planning: Models and algorithms. Transport. Sci. 18, 1--55.
• 33: Magnanti, T. L., Mireault, P., and Wong, R. T.1986. Tailoring benders decomposition for uncapacitated network design. Math. Program. Study 26, 112--154.
• 34: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 35: R. Ravi , R. Sundaram , M. V. Marathe , D. J. Rosenkrantz , S. S. Ravi, Spanning Trees---Short or Small, SIAM Journal on Discrete Mathematics, v.9 n.2, p.178-200, May 1996 [doi>10.1137/S0895480194266331]
• 36: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 37: Wolsey, L. A.1982. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385--393.
• 38: Zelikovsky, A.1997. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18, 99--110.

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, Design, Theory

Keywords:
Optimization, approximation, flow, graphs, theory