Superstrings with multiplicities - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2018

Superstrings with multiplicities

Abstract

A superstring of a set of words P = {s 1 ,. .. , s p } is a string that contains each word of P as substring. Given P , the well known Shortest Linear Superstring problem (SLS), asks for a shortest superstring of P. In a variant of SLS, called Multi-SLS, each word s i comes with an integer m(i), its multiplicity, that sets a constraint on its number of occurrences, and the goal is to find a shortest superstring that contains at least m(i) occurrences of s i. Multi-SLS generalizes SLS and is obviously as hard to solve, but it has been studied only in special cases (with words of length 2 or with a fixed number of words). The approximability of Multi-SLS in the general case remains open. Here, we study the approximability of Multi-SLS and that of the companion problem Multi-SCCS, which asks for a shortest cyclic cover instead of shortest superstring. First, we investigate the approximation of a greedy algorithm for maximizing the compression offered by a superstring or by a cyclic cover: the approximation ratio is 1/2 for Multi-SLS and 1 for Multi-SCCS. Then, we exhibit a linear time approximation algorithm, Concat-Greedy, and show it achieves a ratio of 4 regarding the superstring length. This demonstrates that for both measures Multi-SLS belongs to the class of APX problems.
Fichier principal
Vignette du fichier
multi-super-2018-lipics.pdf (695.48 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01843225 , version 1 (18-07-2018)

Licence

Identifiers

Cite

Eric Rivals, Bastien Cazaux. Superstrings with multiplicities. 29th Annual Symposium on Combinatorial Pattern Matching (CPM), Qingdao University, Jul 2018, Qingdao, China. pp.21:1-21:16, ⟨10.4230/LIPIcs.CPM.2018.21⟩. ⟨lirmm-01843225⟩
264 View
144 Download

Altmetric

Share

More