Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/139312
Citations | ||
Scopus | Web of Scienceยฎ | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Baguley, S. | - |
dc.contributor.author | Friedrich, T. | - |
dc.contributor.author | Neumann, A. | - |
dc.contributor.author | Neumann, F. | - |
dc.contributor.author | Pappik, M. | - |
dc.contributor.author | Zeif, Z. | - |
dc.contributor.editor | Paquete, L. | - |
dc.date.issued | 2023 | - |
dc.identifier.citation | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '23), 2023 / Paquete, L. (ed./s), pp.1537-1545 | - |
dc.identifier.isbn | 9798400701191 | - |
dc.identifier.uri | https://hdl.handle.net/2440/139312 | - |
dc.description.abstract | Parameterized analysis provides powerful mechanisms for obtaining fine-grained insights into different types of algorithms. In this work, we combine this field with evolutionary algorithms and provide parameterized complexity analysis of evolutionary multiobjective algorithms for the๐-separator problem, which is a natural generalization of the vertex cover problem. The goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most๐ vertices. We provide different multi-objective formulations involving two or three objectives that provably lead to fixed-parameter evolutionary algorithms with respect to the value of an optimal solution ๐๐๐ and๐. Of particular interest are kernelizations and the reducible structures used for them. We show that in expectation the algorithms make incremental progress in finding such structures and beyond. The current best known kernelization of the๐-separator uses linear programming methods and requires a non-trivial post-process to extract the reducible structures. We provide additional structural features to show that evolutionary algorithms with appropriate objectives are also capable of extracting them. Our results show that evolutionary algorithms with different objectives guide the search and admit fixed parameterized runtimes to solve or approximate (even arbitrarily close) the๐-separator problem. | - |
dc.description.statementofresponsibility | Samuel Baguley, Tobias Friedrich, Aneta Neumann, Frank Neumann, Marcus Pappik, Ziena Zeif | - |
dc.language.iso | en | - |
dc.publisher | Association for Computing Machinery | - |
dc.rights | ยฉ 2023 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution International 4.0 License. | - |
dc.source.uri | https://dl.acm.org/doi/proceedings/10.1145/3583131 | - |
dc.subject | Evolutionary Algorithms; Parameterized Complexity; Runtime Analysis | - |
dc.title | Fixed Parameter Multi-Objective Evolutionary Algorithms for the W-Separator Problem | - |
dc.type | Conference paper | - |
dc.contributor.conference | Genetic and Evolutionary Computation Conference (GECCO) (15 Jul 2023 - 15 Jul 2023 : Lisbon, Portugal) | - |
dc.identifier.doi | 10.1145/3583131.3590501 | - |
dc.publisher.place | New York, NY | - |
dc.relation.grant | http://purl.org/au-research/grants/arc/FT200100536 | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Neumann, A. [0000-0002-0036-4782] | - |
dc.identifier.orcid | Neumann, F. [0000-0002-2721-3618] | - |
Appears in Collections: | Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hdl_139312.pdf | Published version | 637.49 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.