Skip to Main content Skip to Navigation
Conference papers

Superstrings with multiplicities

Eric Rivals 1, 2 Bastien Cazaux 1, 2
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01843225
Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Wednesday, July 18, 2018 - 4:25:04 PM
Last modification on : Friday, October 22, 2021 - 3:07:27 PM
Long-term archiving on: : Friday, October 19, 2018 - 9:38:47 PM

File

multi-super-2018-lipics.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

978

Files downloads

135