Title | ||
---|---|---|
Fixed-Parameter Tractability Of Crossover: Steady-State Gas On The Closest String Problem |
Abstract | ||
---|---|---|
We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a multi-start (mu+1) GA solves arbitrary length-n instances of closest string in 2(O(d2+dlogk)) center dot t(n) steps in expectation. Here, k is the number of strings in the input set, d is the value of the optimal solution, and n <= t(n) <= poly(n) is the number of iterations allocated to the (mu+1) GA before a restart, which can be an arbitrary polynomial in n. This confirms that the multi-start (mu+1) GA runs in randomized fixed-parameter tractable (FPT) time with respect to the above parameterization. On the other hand, if the crossover operation is disabled, we show there exist instances that require n(Omega(log(d+k))) steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1007/s00453-021-00809-8 | ALGORITHMICA |
Keywords | DocType | Volume |
Runtime analysis, Fixed-parameter tractability, Crossover, Combinatorial optimization | Journal | 83 |
Issue | ISSN | Citations |
4 | 0178-4617 | 1 |
PageRank | References | Authors |
0.36 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrew Sutton | 1 | 20 | 6.82 |