Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem

Research output: Contribution to journalArticlepeer-review

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 (μ+1) GA solves arbitrary length-n instances of closest string in 2O(d2+dlogk)·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 (μ+1) GA before a restart, which can be an arbitrary polynomial in n. This confirms that the multi-start (μ+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Ω(log(d+k)) steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time.

Original languageEnglish (US)
Pages (from-to)1138-1163
Number of pages26
JournalAlgorithmica
Volume83
Issue number4
DOIs
StatePublished - Apr 2021
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature.

Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

Keywords

  • Combinatorial optimization
  • Crossover
  • Fixed-parameter tractability
  • Runtime analysis

Fingerprint Dive into the research topics of 'Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem'. Together they form a unique fingerprint.

Cite this