Yoan Pinzón, Costas S. Iliopoulos, Gad M. Landau and Manal Mohamed

**Approximation Algorithm for the Cyclic Swap Problem**

Abstract: |

Given two n-bit (cyclic) binary strings, A and B,
represented on a circle (necklace instances). Let each sequence
have the same number k of 1's. We are interested in computing
the cyclic swap distance between A and B, i.e., the minimum
number of swaps needed to convert A into B, minimized over all
rotations of B. We show that this distance may be approximated
in O(n+k time.
^{2}) |

Download paper: | ||

PostScript |