Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/127230
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Shi, F. | - |
dc.contributor.author | Neumann, F. | - |
dc.contributor.author | Wang, J. | - |
dc.contributor.editor | Friedrich, T. | - |
dc.contributor.editor | Doerr, C. | - |
dc.contributor.editor | Arnold, D.V. | - |
dc.date.issued | 2019 | - |
dc.identifier.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 | - |
dc.identifier.isbn | 9781450362542 | - |
dc.identifier.uri | http://hdl.handle.net/2440/127230 | - |
dc.description.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. | - |
dc.description.statementofresponsibility | Feng Shi, Frank Neumann, Jianxin Wang | - |
dc.language.iso | en | - |
dc.publisher | Association for Computing Machinery | - |
dc.rights | © 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. | - |
dc.source.uri | http://dx.doi.org/10.1145/3299904.3340314 | - |
dc.subject | Minimum spanning tree | - |
dc.subject | evolutionary algorithm | - |
dc.subject | time analysis | - |
dc.subject | depth restricted (1,2)-minimum spanning tree | - |
dc.title | Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problem | - |
dc.type | Conference paper | - |
dc.contributor.conference | Foundations of Genetic Algorithms (FOGA) (27 Aug 2019 - 29 Aug 2019 : Potsdam, Germany) | - |
dc.identifier.doi | 10.1145/3299904.3340314 | - |
dc.publisher.place | online | - |
dc.relation.grant | http://purl.org/au-research/grants/arc/DP160102401 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Neumann, F. [0000-0002-2721-3618] | - |
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.