Raja Jothi
Abstract
Given an undirected graph G = (V,E) with nonnegative costs on its edges, a root node r V, a set of demands D V with demand v D wishing to route w(v) units of flow (weight) to r, and a positive number k, the Capacitated Minimum Steiner Tree (CMStT) problem asks for a minimum Steiner tree, rooted at r, spanning the vertices in D * {r}, in which the sum of the vertex weights in every subtree connected to r is at most k. When D = V, this problem is known as the Capacitated Minimum Spanning Tree (CMST) problem. Both CMsT and CMST problems are NP-hard. In this article, we present approximation algorithms for these problems and several of their variants in network design. Our main results are the following:
---We present a (³ ÁST + 2)-approximation algorithm for the CMStT problem, where ³ is the inverse Steiner ratio, and ÁST is the best achievable approximation ratio for the Steiner tree problem. Our ratio improves the current best ratio of 2ÁST + 2 for this problem.
---In particular, we obtain (³ + 2)-approximation ratio for the CMST problem, which is an improvement over the current best ratio of 4 for this problem. For points in Euclidean and rectilinear planes, our result translates into ratios of 3.1548 and 3.5, respectively.
---For instances in the plane, under the Lp norm, with the vertices in D having uniform weights, we present a nontrivial (7/5ÁST + 3/2)-approximation algorithm for the CMStT problem. This translates into a ratio of 2.9 for the CMST problem with uniform vertex weights in the Lpmetric plane. Our ratio of 2.9 solves the long-standing open problem of obtaining any ratio better than 3 for this case.
---For the CMST problem, we show how to obtain a 2-approximation for graphs in metric spaces with unit vertex weights and k = 3,4.
---For the budgeted CMST problem, in which the weights of the subtrees connected to r could be up to ± k instead of k (± e 1), we obtain a ratio of ³ + 2/±.
- Aarts, E., and Korst, J. 1989. Simulated Annealing and Boltzman Machines. Wiley, Chichester, U.K.]] Google Scholar
Digital Library
- Ahuja, R., Orlin, J., and Sharma, D. 2001. A composite neighborhood search algorithm for the capacitated minimum spanning tree problem. Oper. Res. Letters 31, 185--194.]]Google ScholarDigital Library
- Altinkemer, K., and Gavish, B. 1988. Heuristics with constant error guarantees for the design of tree networks. Manage. Sci. 34, 331--341.]]Google ScholarDigital Library
- Amberg, A., Domschke, W., and Voß, S. 1996. Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Opt.: Theor. Pract. 1, 9--39.]]Google Scholar
- Boorstyn, R., and Frank, H. 1977. Large-scale network topological optimization. IEEE Trans. Comm. 25, 29--47.]]Google ScholarCross Ref
- Chandy, K., and Lo, T. 1973. The capacitated minimum spanning tree. Networks 3, 173--181.]]Google ScholarCross Ref
- Chandy, K., and Russell, R. 1972. The design of multipoint linkages in a teleprocessing tree network. IEEE Trans. Comp. 21, 1062--1066.]]Google ScholarDigital Library
- Domschke, W., Forst, P., and Voß, S. 1992. Tabu search techniques for the quadratic semi-assignment problem. In New Directions for Operations Research in Manufacturing. Springer, Berlin, Germany, 389--405.]]Google Scholar
- Elias, D., and Ferguson, M. 1974. Topological design of multipoint teleprocessing networks. IEEE Trans. Comm. 22, 1753--1762.]]Google ScholarCross Ref
- Esau, L., and Williams, K. 1966. On teleprocessing system design. IBM Sys. J. 5, 142--147.]]Google ScholarDigital Library
- Frank, H., Frisch, I., Slyke, R. V., and Chou, W. 1971. Optimal design of centralized computer design network. Networks 1, 43--57.]]Google ScholarCross Ref
- Garey, M., and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA.]] Google ScholarDigital Library
- Gavish, B. 1982. Topological design of centralized computer networks---formulations and algorithms. Networks 12, 355--377.]]Google ScholarCross Ref
- Gavish, B. 1983. Formulations and algorithms for the capacitated minimal directed tree problem. J. Assoc. Comput. Mach. 30, 118--132.]] Google ScholarDigital Library
- Gavish, B. 1985. Augmented lagrangean based algorithms for centralized network design. IEEE Trans. Comm. 33, 1247--1257.]]Google ScholarCross Ref
- Gavish, B. 1991. Topological design of telecommunication networks---local access design methods. Ann. Oper. Res. 33, 1, 17--71.]]Google ScholarCross Ref
- Gavish, B., and Altinkemer, K. 1986. Parallel savings heuristics for the topological design of local access tree networks. In Proceedings of the IEEE INFOCOM. 130--139.]]Google Scholar
- Glover, F. 1989. Tabu search---part i. ORSA J. Comput. 1, 190--206.]]Google ScholarCross Ref
- Glover, F. 1990. Tabu search---part ii. ORSA J. Comput. 2, 4--32.]]Google ScholarCross Ref
- Goemans, M., and Williamson, D. 1995. A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296--317.]] Google ScholarDigital Library
- Gouveia, L. 1993. A comparison of directed formulations for the capacitated minimal spanning tree problem. Telecomm. Syst. 1, 51--76.]]Google ScholarDigital Library
- Gouveia, L. 1995. A 2n constraint formulation for the capacitated minimal spanning tree problem. Oper. Res. 43, 130--141.]]Google ScholarDigital Library
- Gouveia, L., and Ao, J. P. 1991. Dynamic programming based heuristics for the topological design of local access networks. Ann. Oper. Res. 33, 305--327.]]Google ScholarCross Ref
- Hall, L. 1996. Experience with a cutting plane approach for the capacitated spanning tree problem. INFORMS J. Comput. 8, 219--234.]]Google ScholarDigital Library
- Hassin, R., Ravi, R., and Salman, F. 2000. Approximation algorithms for capacitated network design problems. In Proceedings of the Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX). 167--176.]] Google ScholarDigital Library
- Jothi, R., and Raghavachari, B. 2004a. Approximation algorithms for the capacitated minimum spanning problem and its variants in network design. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 805--818.]]Google Scholar
- Jothi, R., and Raghavachari, B. 2004b. Survivable network design: The capacitated minimum spanning network problem. Inform Process. Lett. 91, 4, 183--190.]] Google ScholarDigital Library
- Karnaugh, M. 1976. A new class of algorithms for multipoint network optimization. IEEE Trans. Comm. 24, 500--505.]]Google ScholarCross Ref
- Kershenbaum, A. 1974. Computing capacitated minimal spanning trees efficiently. Networks 4, 299--310.]]Google ScholarCross Ref
- Kershenbaum, A., and Boorstyn, R. 1983. Centralized teleprocessing network design. Networks 13, 279--293.]]Google ScholarCross Ref
- Kershenbaum, A., Boorstyn, R., and Oppenheim, R. 1980. Second-order greedy algorithms for centralized teleprocessing network design. IEEE Trans. Comm. 28, 1835--1838.]]Google ScholarCross Ref
- Kershenbaum, A., and Chou, W. 1974. A unified algorithm for designing multidrop teleprocessing networks. IEEE Trans. Comm. 22, 1762--1772.]]Google ScholarCross Ref
- Malik, K., and Yu, G. 1993. A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23, 525--532.]]Google ScholarCross Ref
- Martin, J. 1967. Design of Real-Time Computer Systems. Prentice Hall, Englewood Cliffs, NJ.]] Google ScholarDigital Library
- McGregor, P., and Shen, D. 1977. Network design: An algorithm for the access facility location problem. IEEE Trans. Comm. 25, 61--73.]]Google ScholarCross Ref
- Monma, C., and Suri, S. 1992. Transitions in geometric minimum spanning trees. Disc. Comput. Geom. 8, 265--293.]]Google ScholarDigital Library
- Osman, I., and Christofides, N. 1994. Capacitated clustering problems by hybrid simulated annealing and tabu search. Intl. Trans. Oper. Res. 1, 317--336.]]Google ScholarCross Ref
- Papadimitriou, C. 1978. The complexity of the capacitated tree problem. Networks 8, 217--230.]]Google ScholarCross Ref
- Robins, G., and Salowe, J. 1995. Low-degree minimum spanning trees. Disc. Comput. Geom. 14, 151--166.]]Google ScholarDigital Library
- Salman, F., Cheriyan, J., Ravi, R., and Subramanian, S. 1997. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA). 619--628.]] Google ScholarDigital Library
- Schneider, G., and Zastrow, M. 1982. An algorithm for the design of multilevel concentrator networks. Comput. Netw. 6, 563--581.]]Google Scholar
- Sharaiha, Y., Gendreau, M., Laporte, G., and Osman, I. 1997. A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29, 161--171.]]Google ScholarCross Ref
- Sharma, R., and El-Bardai, M. 1970. Suboptimal communications network synthesis. In Proceedings of the IEEE International Conference on Communications. 19.11--19.16.]]Google Scholar
- Voß, S. 2001. Capacitated minimum spanning trees. In Encyclopedia of Optimization. Kluwer, Boston, MA, 225--235.]]Google Scholar
- Whitney, V. 1970. A study of optimal file assignment and communication network configuration in remote access computer message processing and communications systems. Ph.D. Dissertation. University of Michigan, Ann Arbor, MI.]] Google ScholarDigital Library
Index Terms
- Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
Recommendations
Degree-bounded minimum spanning trees
Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Low-Degree Spanning Trees of Small Weight
Given $n$ points in the plane, the degree-$K$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $K$. This paper addresses the problem of computing low-weight degree-$K$ spanning trees for $K>2$...
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem
AbstractWe consider the problem of finding a minimum diameter spanning tree with maximum node degree $B$ in a complete undirected edge-weighted graph. We provide an $O(\sqrt{\log_Bn})$-approximation algorithm for the problem. Our algorithm is purely ...
Comments