Please use this identifier to cite or link to this item: http://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 / 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)
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.
RMID: 1000011429
DOI: 10.1145/3299904.3340314
Grant ID: http://purl.org/au-research/grants/arc/DP160102401
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.