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.
Type de document :
Communication dans un congrès
Gonzalo Navarro; David Sankoff; Binhai Zhu. CPM: Combinatorial Pattern Matching, Jul 2018, Qingdao, China. Leibniz International Proceedings in Informatics (LIPIcs), 105 (21), pp.21:1-21:16, 2018, 29th Annual Symposium on Combinatorial Pattern Matching. 〈http://cpm2018.sdu.edu.cn/index.html〉. 〈10.4230/LIPIcs.CPM.2018.21〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01843225
Contributeur : Eric Rivals <>
Soumis le : mercredi 18 juillet 2018 - 16:25:04
Dernière modification le : mercredi 10 octobre 2018 - 14:28:13
Document(s) archivé(s) le : vendredi 19 octobre 2018 - 21:38:47

Fichier

multi-super-2018-lipics.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Eric Rivals, Bastien Cazaux. Superstrings with multiplicities. Gonzalo Navarro; David Sankoff; Binhai Zhu. CPM: Combinatorial Pattern Matching, Jul 2018, Qingdao, China. Leibniz International Proceedings in Informatics (LIPIcs), 105 (21), pp.21:1-21:16, 2018, 29th Annual Symposium on Combinatorial Pattern Matching. 〈http://cpm2018.sdu.edu.cn/index.html〉. 〈10.4230/LIPIcs.CPM.2018.21〉. 〈lirmm-01843225〉

Partager

Métriques

Consultations de la notice

239

Téléchargements de fichiers

29