Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The bounded diameter minimum spanning tree problem is an NP-hard combinatorial optimization problem arising, for example, in network design when quality of service is of concern. There exist various exact and metaheuristic approaches addressing this problem, whereas fast construction heuristics are primarily based on Prim's minimum spanning tree algorithm and fail to produce reasonable solutions in particular on large Euclidean instances.

A method based on hierarchical clustering to guide the construction process of a diameter constrained tree is presented. Solutions obtained are further refined using a greedy randomized adaptive search procedure. Based on the idea of clustering we also designed a new neighborhood search for this problem. Especially on large Euclidean instances with a tight diameter bound the results are excellent. In this case the solution quality can also compete with that of a leading metaheuristic, whereas the computation only needs a fraction of the time.

REFERENCES

• 1: Luis Gouveia , Thomas L. Magnanti , Cristina Requejo, A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees, Networks, v.44 n.4, p.254-265, December 2004 [doi>10.1002/net.v44:4]
• 2: M. Gruber and G. R. Raidl. (Meta-)heuristic separation of jump cuts in a branch &cut approach for the bounded diameter minimum spanning tree problem, 2008. submitted to a special issue on Matheuristics of Operations Research/Computer Science Interface Series, Springer
• 3: M. Gruber and G. R. Raidl. Cluster-based (meta-)heuristics for the Euclidean bounded diameter minimum spanning tree problem. In A. Quesada-Arencibia et al., editors, Extended Abstracts of the Twelfth International Conference on Computer Aided Systems Theory (EUROCAST 2009), pages 228--231,Gran Canaria, Spain, 2009
• 4: Martin Gruber , Jano van Hemert , Günther R. Raidl, Neighbourhood searches for the bounded diameter minimum spanning tree problem embedded in a VNS, EA, and ACO, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144185]
• 5: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 6: Bryant A. Julstrom, Greedy heuristics for the bounded diameter minimum spanning tree problem, Journal of Experimental Algorithmics (JEA), 14, August 2009
• 7: R. C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389--1401, 1957
• 8: Günther R. Raidl , Bryant A. Julstrom, Greedy heuristics and an evolutionary algorithm for the bounded-diameter minimum spanning tree problem, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952678]
• 9: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 10: M. Resende and C. Ribeiro. Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 219--249. Kluwer Academic Publishers, 2003
• 11: Alok Singh , Ashok K. Gupta, Improved heuristics for the bounded-diameter minimum spanning tree problem, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.11 n.10, p.911-921, May 2007 [doi>10.1007/s00500-006-0142-y]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms

Keywords:
bounded diameter minimum spanning tree, construction heuristics, dynamic programming, greedy randomized search, local improvement