Stochastic Bounded Diameter Minimum Spanning Tree Problem

• Autorzy: Torkestani J. A.

Identyfikatory

DOI

10.3233/FI-2015-1250

• Języki publikacji: EN

Abstrakty

EN

In this paper, a learning automata-based algorithm is proposed for approximating a near optimal solution to the bounded diameter minimum spanning tree (BDMST) problem in stochastic graphs. A stochastic graph is a graph in which the weight associated with each edge is a random variable. Stochastic BDMST problem seeks for finding the BDMST in a stochastic graph. To the best of our knowledge, no work has been done on solving the stochastic BDMST problem, where the weight associated with the graph edge is random variable. In this study, we assume that the probability distribution of the edges random weight is unknown a priori. This makes the stochastic BDMST problem incredibly hard-to-solve. To show the efficiency of the proposed algorithm, its results are compared with those of the standard sampling method (SSM). Numerical results show the superiority of the proposed sampling algorithm over the SSM both in terms of the sampling rate and convergence rate.

Słowa kluczowe

EN

bounded diameter minimum spanning tree problem; stochastic graph; learning automata; sampling

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 140, nr 2
• Strony: 205--219
• Opis fizyczny: Bibliogr. 48 poz., tab.

Twórcy

autor

Torkestani J. A.

• Department of Computer Engineering Arak Branch, Islamic Azad University, Arak, Iran

Bibliografia

• [1] A. Abdalla, N. Deo, and P. Gupta, Random-tree diameter and the diameter constrained MST, Congressus Numerantium, Vol. 144, pp. 161-182, 2000.
• [2] R. C. Prim. Shortest connection networks and some generalizations, Bell System Technical Journal, Vol. 36, pp. 1389-1401, 1957.
• [3] G. R. Raidl, and B. A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, in: Proceedings of the 2003 ACM Symposium on Applied Computing, pp. 747-752, 2003.
• [4] B. A. Julstrom, Encoding Bounded Diameter Minimum Spanning Trees with Permutations and Random Keys, in: Proceedings of Genetic and Evolutionary Computational Conference (GECCO2004), 2004.
• [5] B. A. Julstrom, and G. R. Raidl, A permutation-coded evolutionary algorithm for the bounded diameter minimum spanning tree problem, in: Genetic and Evolutionary Computation Conferences Workshops Proceedings, Workshop on Analysis and Design of Representations, pp. 2-7, 2003.
• [6] B. A. Julstrom, Encoding bounded-diameter minimum spanning trees with permutations and with random keys, in: Proceedings of the Genetic and Evolutionary Computation Conference, Lecture Note on Computer Science, Vol. 3102, pp. 12821281, 2004.
• [7] G. R. Raidl, and B. A. Julstrom, Edge sets: an effective evolutionary coding of spanning trees, IEEE Transactions on Evolutionary Computation, Vol. 7, No. 3, pp. 225-239, 2003.
• [8] A. Singh, and A. K. Gupta, Improved heuristics for the bounded-diameter minimum spanning tree problem, Soft Computing, Vol. 11, No. 10, pp. 911-921, 2007.
• [9] M. Gruber, and G. R. Raidl, Variable neighborhood search for the bounded diameter minimum spanning tree problem, in: Proceedings of the 18th Mini Euro Conference on Variable Neighborhood Search, Tenerife, Spain, 2005.
• [10] H. Binh, N. Hoai, and R. I. McKay, A New Hybrid Genetic Algorithm for Solving the Bounded Diameter Minimum Spanning Tree Problem, in: Proceedings of IEEE World Congress on Computational Intelligence (CEC2008), 2008, pp.3127-3133.
• [11] H. Binh, and N. Nghia, New multiparent Recombination in Genetic Algorithm for Solving Bounded Diameter Minimum Spanning Tree Problem, in: Proceedings of 1st Asian Conference on Intelligent Information and Database Systems, pp. 283-288, 2009.
• [12] C. Requejo, and E. Santos, Greedy Heuristics for the Diameter-constrained Minimum Spanning Tree Problem, Journal of Mathematical Sciences, Vol. 161, No. 6, pp. 930-943, 2009.
• [13] T. A. Feo, and M. G. C. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operation Research Letters, Vol. 8, pp. 67-71, 1989.
• [14] H. R. Loureno, O. C. Martin, and T. Stutzle, Iterated local search, Handbook of Metaheuristics, Kluwer, pp. 321-353, 2002.
• [15] A. Lucena, C. C. Ribeiro, and A. C. Santos, A hybrid heuristic for the diameter constrained minimum spanning tree problem, Journal of Global Optimization, Vol. 46, pp. 363-381, 2010.
• [16] M. Gruber, J. Hemert, and G. R. Raidl, Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA and ACO, in: Proceedings of Genetic and Evolutionary Computational Conference (GECCO2006), 2006.
• [17] A. C. Santos, A. Lucena, and C. C. Ribeiro, Solving diameter constrained minimum spanning tree problem in dense graphs, Lecture Notes on Computer Science, Vol. 3059, pp. 458467, 2004.
• [18] L. Gouveia, and T. L. Magnanti, Modelling and Solving the Diameter-Constrained Minimum Spanning Tree Problem, Technical Report, Departamento de Estatstica e Investiga?o Operational, Faculdade de Ci?ncias, Lisboa, 2000.
• [19] E. J. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, Vol. 41, No. 11, pp. 1069-1072, 1990.
• [20] E. J. Beasley, OR-Library: Capacitated MST, http://people.brunel.ac. uk/ mastjjb/jeb/orlib/capmstinfo.html, 2005.
• [21] L. Gouveia, T. L. Magnanti, and C. Requejo, A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees, Networks, Vol. 44, pp. 254-265, 2004.
• [22] L. Gouveia, and T. L. Magnanti, Network Flow Models for Designing Diameter- Constrained Minimum-Spanning and Steiner Trees, Netwoks, Vol. 4, No. 3, pp. 159-173, 2003.
• [23] T. N. Bui, and C. M. Zrncic, An Ant-based Algorithm for Finding Degree-Constrained Minimum Spanning Tree, in: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp. 11-18, 2006.
• [24] T. Oncan, Design of Capacitated Minimum Spanning Tree with Uncertain Cost and Demand Parameters, Information Sciences, Vol. 177, pp. 4354-4367, 2007.
• [25] T. Oencan, J. F. Cordeau, and G. Laporte, A Tabu Search Heuristic for the Generalized Minimum Spanning Tree Problem, European Journal of Operational Research, Vol. 191, No.2, pp.306-319, 2008.
• [26] M. Parsa, Q. Zhu, and J. J. Garcia-Luna-Aceves, An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting, IEEE/ACM Transactions on Networking, Vol. 6, No. 4, pp. 461-474, 1998.
• [27] H. F. Salama, D. S. Reeves, and Y. Viniotis, The Delay-Constrained Minimum Spanning Tree Problem, in Proceedings of the Second IEEE Symposium on Computers and Communications, pp. 699-703, 1997.
• [28] L. Gouveia, L. Simonetti, and E. Uchoa, Modeling Hop-constrained and Diameter-constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs, Journal of Mathematical Programming, 2009.
• [29] J. B. Kruskal, On the Shortest Spanning Sub Tree of a Graph and the Traveling Salesman Problem, in Proceedings of Amer. Math. Soc, Vol. pp. 748-750, 1956.
• [30] L. Hanr, and Y. Wang, A Novel Genetic Algorithm for Degree-Constrained Minimum Spanning Tree Problem, International Journal of Computer Science and Network Security, Vol. 6, No.7A, pp. 50-57, 2006.
• [31] M. Krishnamoorthy, and A. Ernst, Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree, Journal of Heuristics, Vol. 7, pp. 587-611, 2001.
• [32] Y. M. Sharaiha, M. Gendreau, G. Laporte, and I. H. Osman, A Tabu Search Algorithm for the Capacitated Shortest Spanning Tree Problem, Networks, Vol. 29, No. 3, pp. 161-171, 1998.
• [33] R. M. Karp, Reducibility among Combinatorial Problems, Complexity of Computer Computations, Plenum Press, USA, pp. 85-103, 1972.
• [34] K. Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems, Vol. 7, No.1, pp. 61-77, 1989.
• [35] A. Bookstein, and S. T. Klein, Compression of correlated bitvectors, Information Systems, Vol. 16, pp. 110-118, 2001.
• [36] N. R. Achuthan, L. Caccetta, P. Caccetta, and A. Geelen, Computational Methods for the Diameter Restricted Minimum Weight Spanning Tree Problem, Australian Journal of Combinatorics, Vol. 10, pp. 51-71, 1994.
• [37] M. Gruber and G. R. Raidl, A New 0-1 ILP Approach for the Bounded Diameter Minimum Spanning Tree Problem, in Proceedings of the 2nd International Network Optimization Conference, 2005.
• [38] V. Aggarwal, Y. Aneja, and K. Nair, Minimal Spanning Tree Subject to a Side Constraint, Computer Operations Research, Vol. 9, pp. 287-296, 1982.
• [39] K. S. Narendra, and K. S. Thathachar, Learning automata: An introduction, New York, Printice-Hall, 1989.
• [40] M. A. L. Thathachar, and B. R. Harita, Learning automata with changing number of actions, IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMG17, pp. 1095-1100, 1987.
• [41] J. Akbari Torkestani, and M. R. Meybodi Learning Automata-Based Algorithms for Finding Minimum Weakly Connected Dominating Set in Stochastic Graphs, International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, Vol. 18, No. 6, pp. 721-758, 2010.
• [42] A. Ballardie, P. Francis, and J. Crowcroft, Core-based trees (CBT)- An architecture for scalable inter-domain multicast routing, Computer Communication Review, Vol. 23, No. 4, pp. 85-95, 1993.
• [43] H. Ishii, S. Shiode, T. Nishida and Y. Namasuya, ”Stochastic Spanning Tree Problem,” Discrete Applied Mathematics, 1981, Vol. 3, pp. 263-273.
• [44] H. Ishii and T. Nishida, ”Stochastic Bottleneck Spanning Tree Problem,” Networks, 1983, Vol. 13, pp. 443-449.
• [45] I. B. Mohd, ”Interval Elimination Method for Stochastic Spanning Tree Problem,” Applied Mathematics and Computation, 1994, Vol. 66, pp. 325-341.
• [46] H. Ishii and T. Matsutomi, ”Confidence Regional Method of Stochastic Spanning Tree Problem,” Mathl. Comput. Modelling Vol. 22, No. 19-12, 1995, pp. 77-82.
• [47] C. Alexopoulos and J. A. Jacobson, ”State Space Partition Algorithms for Stochastic Systems with Applications to Minimum Spanning Trees,” Networks, Vol. 35, No.2, 2000, pp. 118.138.
• [48] K. R. Hutson, and D. R. Shier, Minimum Spanning Trees in Networks with varying Edge Weights, Annals of Operations Research, Vol. 146, pp. 318, 2006.