Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10347632 | Computers & Operations Research | 2012 | 9 Pages |
Abstract
The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Shunji Tanaka,