Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problem|
|Citation:||FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2019 / pp.133-146|
|Publisher:||Association for Computing Machinery|
|Conference Name:||Foundations of Genetic Algorithms (FOGA) (27 Aug 2019 - 29 Aug 2019 : Potsdam, Germany)|
|Feng Shi, Frank Neumann, Jianxin Wang|
|Abstract:||The Minimum Spanning Tree problem is a well-known combinatorial optimization problem, which has attracted much attention from the researchers in the field of evolutionary computing. Within the paper, a constrained version of the problem named Depth Restricted (1-2)-Minimum Spanning Tree problem is considered in the context of evolutionary algorithms, which had been shown to be NP-hard. We separately investigate the expected time (i.e., the expected number of fitness evaluations) of the (1+1) EA, the Multi-Objective Evolutionary Algorithm and its two variants adapted to the constrained version, to obtain an approximate solution with ratio 2 or 3/2 with respect to several different fitness functions. In addition, we observe a close connection between the constrained version and the Set Cover problem, and present a simple evolutionary algorithm for the 3-Set Cover problem. Based on the approximate solution returned by our evolutionary algorithm for the 3-Set Cover problem, an approximate solution with ratio better than 3/2 for the constrained version can be constructed.|
|Keywords:||Minimum spanning tree; evolutionary algorithm; time analysis; depth restricted (1,2)-minimum spanning tree|
|Rights:||© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.|
|Appears in Collections:||Computer Science publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.