Parameterized complexity analysis of evolutionary algorithms
Pages 607 - 622
References
[1]
Karl Bringmann and Tobias Friedrich. Parameterized average-case complexity of the hypervolume indicator. In Proceedings of the ACM Genetic and Evolutionary Computation Conference (GECCO), pages 575-582. ACM Press, 2013.
[2]
Dogan Corus, Per Kristian Lehre, and Frank Neumann. The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation. In Christian Blum and Enrique Alba, editors, GECCO, pages 519-526. ACM, 2013.
[3]
Stefan Kratsch, Per Kristian Lehre, Frank Neumann, and Pietro Oliveto. Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation. In Robert Schaefer, Carlos Cotta, Joanna Kolodziej, and Günter Rudolph, editors, Parallel Problem Solving from Nature - PPSN XI, volume 6238 of Lecture Notes in Computer Science, pages 204-213. Springer Berlin / Heidelberg, 2011.
[4]
Stefan Kratsch and Frank Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754-771, 2013.
[5]
Samadhi Nallaperuma, Andrew M. Sutton, and Frank Neumann. Fixed-parameter evolutionary algorithms for the Euclidean traveling salesperson problem. In Evolutionary Computation (CEC), 2013 IEEE Congress on, pages 2037-2044, 2013.
[6]
Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer, 2010.
[7]
Andrew M. Sutton, Jareth Day, and Frank Neumann. A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), 2012.
[8]
Andrew M. Sutton and Frank Neumann. A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In Carlos A. Coello Coello, Vincenzo Cutello, Kalyanmoy Deb, Stephanie Forrest, Giuseppe Nicosia, and Mario Pavone, editors, Parallel Problem Solving from Nature - PPSN XII, volume 7491 of Lecture Notes in Computer Science, pages 52-61. Springer Berlin Heidelberg, 2012.
[9]
Andrew M. Sutton, Frank Neumann, and Samadhi Nallaperuma. Parameterized runtime analyses of evolutionary algorithms for the planar Euclidean traveling salesperson problem. Evolutionary Computation, (in press), 2014.
Index Terms
- Parameterized complexity analysis of evolutionary algorithms
Recommendations
Parameterized Complexity of Graph Burning
AbstractGraph Burning asks, given a graph and an integer k, whether there exists such that every vertex in G has distance at most i from some . This problem is known to be NP-complete even on connected caterpillars of maximum ...
Parameterized complexity dichotomy for Steiner Multicut
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = { T 1 , ź , T t } , T i ź V ( G ) , of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that ...
On parameterized exponential time complexity
In this paper we study the notion of parameterized exponential time complexity. We show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time O(2^@d^f^(^k^)q(n)) for any constant @d>0, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2014
1524 pages
Copyright © 2014 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2014
Check for updates
Author Tags
Qualifiers
- Tutorial
Conference
GECCO '14
Sponsor:
Acceptance Rates
GECCO Comp '14 Paper Acceptance Rate 180 of 544 submissions, 33%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 73Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in