An approximation algorithm for the balanced capacitated minimum spanning tree problem

Document Type : Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, P.O. Box 15875-4413, Iran

Abstract

The capacitated minimum spanning tree problem (CMSTP), a well-known combinatorial optimiza-
tion problem, holds a central place in telecommunication network design. This problem is to fi nd a minimum
cost spanning tree with an extra cardinality limitation on the orders of the subtrees incident to a certain root
node. The balanced capacitated minimum spanning tree problem (BCMSTP) is a special case that aims to balance the orders of the subtrees. We show this problem is NP-hard and present two approximation algorithms,
in this paper.
Considering the maximum order of the subtrees Q, we provide a (3 - 1
/Q)-approximation algorithm to find a
balanced solution. We improve this result to a (2:5 + \epsilon)-approximation algorithm (for every given \epsilon > 0), in
the 2d-Euclidean spaces. Also, we present a polynomial time approximation scheme (PTAS) for CMSTP.

Keywords


References:
1. Oncan, T. and Altinel, I. K. \Parametric enhancements of the Esau-Williams heuristic for the capacitated minimum spanning
tree problem\, Journal of the Operational Research Society, 60, pp. 259-267 (2009).
2. Ali, A. I. and Huang, C. H. \Balanced spanning forests and trees\, Networks, 21(6), pp. 667-687 (1991).
3. Arkin, E. M. and Guttmann-Beck, N. and Hassin, R. \The (K,k)-capacitated spanning tree problem\, International Conference on Algorithmic Applications in Management, Algorithmic Aspects in Information and Management, pp. 25-34 (2010).
4. Gavish, B. \Topological design of centralized computer networks-formulations and algorithms\, Networks, 12, pp. 355-377(1982).
5. Hassin, R. and Ravi, R. and Salman, F. S. \Approximation algorithms for capacitated network design problems\, APPROX,
pp. 167-176 (2000).
6. Kritikos, M. and Ioannou, G. \A greedy heuristic for the capacitated minimum spanning tree problem\, Journal of the
Operational Research Society, 68, pp. 1223-1235 (2017).
7. Ruiza, E. and Albareda-Sambola, M. and Fernndez, E., et al. \A biased random-key genetic algorithm for the capacitated
minimum spanning tree problem\, Journal Computers and Operations Research, 57, pp. 95-108 (2015).
8. Sharma, R. L. \Design of an economical multidrop network topology with capacity constraints\, IEEE Transactions on
Communications, 31, pp. 590-591 (1983).
9. Incel, O. D. and Ghosh, A. and Krishnamachari, B., et al.\Fast data collection in tree-based wireless sensor networks\, IEEE
Transactions on Mobile Computing, 11(1), pp. 86-99 (2012).
10. Vazirani, V. V. \Approximation algorithms\, Springer (2001).
11. Bowerman, R. and Hall, B. and Calamai, P. \A Multi objective optimization approach to urban school bus routing: formulation and solution method\, Transportation Research Part A: Policy and Practice, 29, pp. 107-123 (1995).
12. Ate , R. and Salari, M. and Coelho, L. C., et al. \The open vehicle routing problem with decoupling points\, European Journal of Operational Research, 265(1), pp. 316-327 (2018).
13. Jothi, R. and Raghavachari, B. \Approximation algorithms for the capacitated minimum spanning tree problem and its
variants in network design\, ACM Transactions on Algorithms, 1, 265-282 (2005).
14. Martello, S. and Pulleyblank, W. R. and Toth, P., et al. \Balanced optimization problems\, Operations Research Letters, 3, pp. 275-278 (1984).
15. Bassetto, T. and Mason, F. \The 2-period balanced traveling salesman problem\, RePEc: vnm: wpaper, 154 (2007).
16. Cappanera, P. and Scutella, M. G. \Balanced paths in a cyclic networks: tractable cases and related approaches\, Networks,
45, pp. 104-111 (2005).
17. da Cunha, A.S. \Formulation and branch-and-cut algorithm for the minimum cardinality balanced and connected clustering problem\, In Proceedings of the International Network Optimization Conference (INOC), Avignon, France, June 12-14 (2019).
18. Feldmann, A. E. and Foschini, L. \Balanced partitions of trees and applications\, Algorithmica, 71, pp. 354-376 (2015).
19. Ficker, A. and Spieksma, F. C. and Woeginger, G. J. \Balanced vector optimization\, KUL, Research Report (2016).
20. Kinable, J. and Smeulders, B. and Delcour, E., et al. \Exact algorithms for the equitable traveling salesman problem\, European Journal of Operational Research, 261, pp. 475-485 (2017).
21. Youse khoshbakht, M. and Didehvar, F. and Rahmati, F. \An e ective rank based ant system algorithm for solving the balanced vehicle routing problem\, International Journal of Industrial Engineering, 23 (2016).
22. Zhang, H. \Balanced graph partitioning: optimizing graph cut based on label swapping\, International Conference on Behavioral, Economic and Socio-cultural Computing (BESC), Nanjing, China, 30 Oct. - 1 Nov. (2015).
23. Gavish, B. and Altinkemer, K. \A parallel savings heuristic for the topological design of local access tree networks\, Proceedings IEEE-INFOCOM'86, pp. 130-139 (1986).
24. Altinkemer, K. and Gavish, B. \Heuristics with constant error guarantees for the design of tree networks\, Management Science, 34, pp. 331-341 (1988).
25. Gavish, B. \Augmented lagrangean based algorithms for centralized network design\, IEEE Transactions on Communica-
tions, 33, pp. 1247-1257 (1985).
26. Kershenbaum, A. and Boorstyn, R. \Centralized teleprocessing network design\, Networks, 13, pp. 279-293 (1983).
27. Ahuja, R. and Orlin, J. and Sharma, D. \A composite neighborhood search algorithm for the capacitated minimum spanning tree problem\, Operations Research Letters, 31, pp. 185-194 (2003).
28. Chandy, K. M. and Lo, T. \The capacitated minimum tree\, Networks, 3, pp. 173-182 (1973).
29. Gavish, B. \Topological design of telecommunication networks local access design methods\, Annals of Operations Research, 33, pp. 17-71 (1991).
30. Gouveia, L. \A comparison of directed formulations for the capacitated minimal spanning tree problem\, Telecommunication Systems, 1, pp. 51-76 (1993).
31. Gamvros, I. and Golden, B. and Raghavan, S. \The multilevel capacitated minimum spanning tree problem\, INFORMS
Journal on Computing, 18, pp. 348-365 (2006).
32. Berger, D. and Gendron, B. and Potvin, J. Y., et al. \Tabu search for a network loading problem with multiple facilities\, Journal of Heuristics, 6, pp. 253-267 (2000).
33. Salman, F. S. and Ravi, R. and Hooker, J. \Solving the local access network design problem\, Working paper, Krannert Graduate School of Management, Purdue University, West Lafayette (2001).
34. Rothfarb, B. and Goldstein, M. C. \The one-terminal Telpak problem\, Operations Research, 19, pp. 156-169 (1971).
35. Salman, F. S. and Cheriyan, J. and Ravi, R., et al. \Buy-at-bulk network design: Approximating the single-sink edge installation problem\, Proceedings 8th ACM-SIAM symposium on Discrete Algorithms (SODA), pp. 619-628 (1997).
36. Jothi, R. and Raghavachari, B. \Survivable network design: The capacitated minimum spanning network problem\, Infor-
mation Processing Letters, 91, pp. 183-190 (2004).
37. Goemans, M. X. and Williamson, D. P. \A general approximation technique for constrained forest problems\, SIAM Journal on Computing, 24(2), pp. 296-317 (1995).
38. Ruiz, H. E. R. \The capacitated minimum spanning tree problem\, Ph.D. Thesis, Universitat Politecnica de Catalunya, BarcelonaTech (2013).
39. Chen, J. and Chen, S. \Optimization of vehicle routing problem with load balancing and time windows in distribution\, 4th International Conference on Wireless Communications, Networking and Mobile Computing (2008). DOI: 10.1109/WiCom.2008.1527
40. Fallah, H. and Didehvar, F. and Rahmati, F. \Approximation algorithms for the load-balanced capacitated vehicle routing
problem\, Bulletin of the Iranian Mathematical Society (2020). DOI: 10.1007/s41980-020-00440-3 14 Haniyeh Fallah et al.
41. Cowell, F. A. \Measurement of inequality\, In handbook of income distribution, A. B. Atkinson, and F. Bourguignon, Ed.,
North Holland, Amsterdam (2000).
42. Garey, M. R. and Johnson, D. S. \Computers and intractability: a guide to the theory of NP-completeness\ (1979).
43. Papadimitriou, C. H. \The Complexity of the capacitated tree problem\, Networks, 8, pp. 217-230 (1978).
44. Camerini, P. M. and Galbiatai, G. and Ma oli, F. \Complexity of spanning tree problems: part 1\, European Journal of Operational Research, 5, pp. 346-352 (1980).
45. Camerini, P. M. and Maoli, F. and Martello, S., et al.\Most and least uniform spanning trees\, Discrete Applied Mathe matics, 15, pp. 181-187 (1986).
46. Beasley, J. \Route  rst-cluster second methods for vehicle routing\, Omega, 11, pp. 403-408 (1983).
47. Haimovich, M. and Rinnooy Kan, A. H. G. \Bounds and heuristics for capacitated routing problems\, Mathematics of Operations Research, 10, pp. 527-524 (1985).
48. Khachay, M. and Dubinin, R. \PTAS for the euclidean capacitated vehicle routing problem in Rd\, International Conference
on Discrete Optimization and Operations Research, Lecture Notes in Computer Science 9869, pp. 193-205 (2016).
Volume 28, Special issue on collective behavior of nonlinear dynamical networks
Transactions on Computer Science & Engineering and Electrical Engineering (D)
June 2021
Pages 1479-1492
  • Receive Date: 27 August 2019
  • Revise Date: 21 September 2020
  • Accept Date: 18 October 2020