Iterative Rounding for the Closest String Problem

Details Iterative Rounding for the Closest String Problem Iterative Rounding for the Closest String Problem

2007-05-04

arxiv.org/abs/0705.0561v2

Computer Science

Data Structures and Algorithms

This paper has been published in abstract Booklet of CiE09

Scientific paper

The closest string problem is an NP-hard problem, whose task is to find a string that minimizes maximum Hamming distance to a given set of strings. This can be reduced to an integer program (IP). However, to date, there exists no known polynomial-time algorithm for IP. In 2004, Meneses et al. introduced a branch-and-bound (B & B) method for solving the IP problem. Their algorithm is not always efficient and has the exponential time complexity. In the paper, we attempt to solve efficiently the IP problem by a greedy iterative rounding technique. The proposed algorithm is polynomial time and much faster than the existing B & B IP for the CSP. If the number of strings is limited to 3, the algorithm is provably at most 1 away from the optimum. The empirical results show that in many cases we can find an exact solution. Even though we fail to find an exact solution, the solution found is very close to exact solution.

Affiliated with

Also associated with

No associations

Rating

Iterative Rounding for the Closest String Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Iterative Rounding for the Closest String Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative Rounding for the Closest String Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615110