Title: A local search 2.917-approximation algorithm for duo-preservation string mapping,
Abstract: We study the {\em maximum duo-preservation string mapping} ({\sc Max-Duo})
problem, which is the complement of the well studied {\em minimum common string
partition} ({\sc MCSP}) problem. Both problems have applications in many fields
including text compression and bioinformatics. Motivated by an earlier local
search algorithm, we present an improved approximation and show that its
performance ratio is no greater than ${35}/{12} < 2.917$. This beats the
current best $3.25$-approximation for {\sc Max-Duo}. The performance analysis
of our algorithm is done through a complex yet interesting amortization. Two
lower bounds on the locality gap of our algorithm are also provided.