New insights into the OCST problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

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

New insights into the OCST problem: integrating node degrees and their location in the graph

Full text

Pdf (377 KB)

Source

Genetic And Evolutionary Computation Conference archive
Proceedings of the 11th Annual conference on Genetic and evolutionary computation table of contents

Montreal, Québec, Canada

SESSION: Track 4: combinatorial optimization and metaheuristics table of contents

Pages: 357-364

Year of Publication: 2009

ISBN:978-1-60558-325-9

Authors

Wolfgang Steitz	University of Mainz, Mainz, Germany
Franz Rothlauf	University of Mainz, Mainz, Germany

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 32, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1569901.1569951 What is a DOI?

ABSTRACT

This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the center of the network are more likely to be included in good solutions. We add to the literature and provide additional insights into the structure of the OCST problem. Therefore, we investigate properies of the whole tree, such as node degrees and the Wiener index. The results reveal that optimal solutions are structured in a star-like manner. There are few nodes with high node degrees, these nodes are located next to the graph's center. The majority of the nodes have very low node degrees. Especially, nodes with degree one are very common and located far away of the center. We exploit these insights to develop a construction heuristic, which builds spanning trees with similar properties. Experiments indicate a high solution quality for the OCST problem. In a next step, we seed the initial population of an evolutionary algorithm (EA) with solutions constructed with our method. An experimental study demonstrates the merits of using a biased initialization: the algorithm is faster, better compared to the same algorithm using random starting solutions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. K. Ahuja , V. V. S. Murty, New lower planes for the network design problem, Networks, v.17 n.2, p.113-127, Summer 1987 [doi>10.1002/net.3230170202]
	2	R. K. Ahuja and V. V. S. Murty. Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem. Transportation Science, 21(3):163--170, 1987.
	3	R. Aringhieri , P. Hansen , F. Malucelli, A Linear Algorithm for the Hyper-Wiener Number of Chemical Trees, University of Pisa, 1999
	4	R. Diestel. Graph Theory. Springer, 3 edition, 2005.
	5	S. Even. Algorithmic Combinatorics. The Macmillan Company, New York, 1973.
	6	T. Fischer and P. Merz. A Memetic Algorithm for the Optimum Communication Spanning Tree Problem. In T. Bartz-Beielstein, M. J. B. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels, editors, Hybrid Metaheuristics, volume 4771, pages 170--184. Springer, 2007.
	7	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
	8	T. C. Hu. Optimum Communication Spanning Trees. SIAM Journal on Computing, 3(3):188--195, 1974.
	9	Yu Li , Youcef Bouchebaba, A New Genetic Algorithm for the Optimal Communication Spanning Tree Problem, Selected Papers from the 4th European Conference on Artificial Evolution, p.162-173, November 03-05, 1999
	10	Charles Campbell Palmer, An approach to a problem in network design using genetic algorithms, Polytechnic University, Brooklyn, NY, 1994
	11	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	12	T. Paulden. Combinatorial spanning tree representations for evolutionary algorithms. PhD thesis, University of Exeter, September 2007.
	13	T. Paulden. Combinatorial spanning tree representations for evolutionary algorithms. PhD thesis, University of Exeter, September 2007.
	14	H. Prufer. Neuer Beweis eines Satzes uber Permutationen. Archiv fur Mathematik und Physik, 27:742--744, 1918.
	15	G. Raidl. An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Problem. In Proc. of the 2000 Congress on Evolutionary Computation, pages 104--111, Piscataway, NJ, 2000. IEEE Service Center.
	16	G. R. Raidl and B. A. Julstrom. Edge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3):225--239, 2003.
	17	E. Reshef. Approximating minimum communication cost spanning trees and related problems. Master's thesis, Feinberg Graduate School of the Weizmann Institute of Science, Rehovot 76100, Israel, April 1999.
	18	Gabriel Robins , Jeffrey S. Salowe, On the maximum degree of minimum spanning trees, Proceedings of the tenth annual symposium on Computational geometry, p.250-258, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177978]
	19	Franz Rothlauf, Representations for Genetic and Evolutionary Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
	20	Franz Rothlauf , David E. Goldberg , Armin Heinzl, Network random keys: a tree representation scheme for genetic and evolutionary algorithms, Evolutionary Computation, v.10 n.1, p.75-97, Spring 2002 [doi>10.1162/106365602317301781]
	21	F. Rothlauf and A. Heinzl. On Optimal Solutions for the Optimal Communication Spanning Tree Problem. Technical report, Department of Information Systems 1, University of Mannheim, 2003.
	22	F. Rothlauf and C. Tzschoppe. On the Bias and Performance of the Edge-Set Encoding. Technical Report 11, Department of Information Systems 1, University of Mannheim, 2004.
	23	P. Sharma. Algorithms for the optimum communication spanning tree problem. Annals of Operations Research, 143(1):203--209, 2006.
	24	Sang-Moon Soak, A New Evolutionary Approach for the Optimal Communication Spanning Tree Problem, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E89-A n.10, p.2882-2893, October 2006 [doi>10.1093/ietfec/e89-a.10.2882]
	25	Wolfgang Steitz , Franz Rothlauf, Orientation matters: how to efficiently solve ocst problems with problem-specific EAs, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389205]
	26	Patrick D. Surry , Nicholas J. Radcliffe, Inoculation to Initialise Evolutionary Search, Selected Papers from AISB Workshop on Evolutionary Computing, p.269-285, April 01-02, 1996
	27	B. Y. Wu and K.-M. Chao. Spanning Trees and Optimization Problems. CRC Press, 2004.
	28	Bang Ye Wu , Kun-Mao Chao , Chuan Yi Tang, A polynomial time approximation scheme for optimal product-requirement communication spanning trees, Journal of Algorithms, v.36 n.2, p.182-204, Aug. 2000 [doi>10.1006/jagm.2000.1088]
	29	Bang Ye Wu , Kun-Mao Chao , Chuan Yi Tang, Approximation algorithms for some optimum communication spanning tree problems, Discrete Applied Mathematics, v.102 n.3, p.245-266, June 2000 [doi>10.1016/S0166-218X(99)00212-7]