On improving the approximation ratio of the r-shortest common superstring problem

2018/04/30 by Braquelaire, Tristan, Gasparoux, Marie, Raffinot, Mathieu +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.00060

Abstract

The Shortest Common Superstring problem (SCS) consists, for a set of strings S = s₁,...,s_n, in finding a minimum length string that contains all s_i, 1<= i <= n, as substrings. While a 2+11/30 approximation ratio algorithm has recently been published, the general objective is now to break the conceptual lower bound barrier of 2. This paper is a step ahead in this direction. Here we focus on a particular instance of the SCS problem, meaning the r-SCS problem, which requires all input strings to be of the same length, r. Golonev et al. proved an approximation ratio which is better than the general one for r<= 6. Here we extend their approach and improve their approximation ratio, which is now better than the general one for r<= 7, and less than or equal to 2 up to r = 6.

Related

• All instantiations of the greedy algorithm for the shortest superstring problem are equivalent
• An Algorithm for a Variation of the Shortest Common Superstring Problem
• Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
• Collapsing Superstring Conjecture
• Greedy Shortest Common Superstring Approximation in Compact Space