Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/127230
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problem |
Author: | Shi, F. Neumann, F. Wang, J. |
Citation: | FOGA '19: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, 2019 / Friedrich, T., Doerr, C., Arnold, D.V. (ed./s), pp.133-146 |
Publisher: | Association for Computing Machinery |
Publisher Place: | online |
Issue Date: | 2019 |
ISBN: | 9781450362542 |
Conference Name: | Foundations of Genetic Algorithms (FOGA) (27 Aug 2019 - 29 Aug 2019 : Potsdam, Germany) |
Editor: | Friedrich, T. Doerr, C. Arnold, D.V. |
Statement of Responsibility: | 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. |
DOI: | 10.1145/3299904.3340314 |
Grant ID: | http://purl.org/au-research/grants/arc/DP160102401 |
Published version: | http://dx.doi.org/10.1145/3299904.3340314 |
Appears in Collections: | Aurora harvest 8 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.