A new heuristic algorithm for the closest string problem

Finding a string that is close to each string in a given set of strings is called the closest string problem (CSP). The problem is known to be NP-hard, which arises in computational molecular biology and coding theory. The paper presents a simple and efficient heuristic, which can provide a better upper bound on the value of an optimal solution to CSP. That is, the quality of our algorithm is better than that of the known algorithm. By our simulations, the maximum approximation ratio (the approximation solution, over the optimal solution obtained by linear programming relaxation) by our algorithm is about 1.062, while that of the algorithm introduced by Meneses et al. in 2004 is about 1.218.