Abstract: In the Shortest-Superstring problem, we are given a set of strings S and want to find a string that contains all strings in S as substrings and has minimum length. This is a classical problem in approximation and the best known approximation factor is 2 1/2, given by Sweedyk in 1999. Since then no improvement has been made, howerever two other approaches yielding a 2 1/2-approximation algorithms have been proposed by Kaplan et al. and recently by Paluch et al., both based on a reduction to maximum asymmetric TSP path (Max-ATSP-Path) and structural results of Breslauer et al. In this paper we give an algorithm that achieves an approximation ratio of 2 11/23, breaking through the long-standing bound of 2 1/2. We use the standard reduction of Shortest-Superstring to Max-ATSP-Path. The new, somewhat surprising, algorithmic idea is to take the better of the two solutions obtained by using: (a) the currently best 2/3-approximation algorithm for Max-ATSP-Path and (b) a naive cycle-cover based 1/2-approximation algorithm. To prove that this indeed results in an improvement, we further develop a theory of string overlaps, extending the results of Breslauer et al. This theory is based on the novel use of Lyndon words, as a substitute for generic unbordered rotations and critical factorizations, as used by Breslauer et al.
Recommendations
Cited in
(20)- Relationship between superstring and compression measures: new insights on the greedy conjecture
- Inverse Lyndon words and inverse Lyndon factorizations of words
- On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
- All instantiations of the greedy algorithm for the shortest common superstring problem are equivalent
- Dynamic and internal longest common substring
- Solving SCS for bounded length strings in fewer than \(2^n\) steps
- A linear time algorithm for shortest cyclic cover of strings
- Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence
- A probabilistic PTAS for shortest common superstring
- Rotations of Periodic Strings and Short Superstrings
- Approximating shortest superstring problem using de Bruijn graphs
- 2D Lyndon words and applications
- Practical lower and upper bounds for the shortest linear superstring
- Longest Lyndon Substring After Edit
- Greedy shortest common superstring approximation in compact space
- The ``runs theorem
- Collapsing Superstring Conjecture
- Approximation guarantees for shortest superstrings: simpler and better
- Finding an optimal alphabet ordering for Lyndon factorization is hard
- On the greedy algorithm for the shortest common superstring problem with reversals
This page was built for publication: Lyndon words and short superstrings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741777)
