3-Shortest Superstring is 2-approximable by a greedy algorithm

Bastien Cazaux 1, 2 Eric Rivals 1, 2, *
* Auteur correspondant
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 is a string that contains each input word as a sub-string. Given such a set, the Shortest Superstring Problem (SSP) asks for a super-string of minimum length. SSP is an important theoretical problem related to the Asymmetric Travelling Salesman Problem, and also has practical applications in data compression and in bioinformatics. Indeed, it models the question of assembling a genome from a set of sequencing reads. Unfortunately, SSP is known to be NP-hard even on a binary alphabet and also hard to approximate with respect to the superstring length or to the compression achieved by the superstring. Even the variant in which all words share the same length r, called r-SSP, is NP-hard whenever r > 2. Numerous involved approximation algorithms achieve approximation ratio above 2 for the superstring, but remain difficult to implement in practice. In contrast the greedy conjecture asked in 1988 whether a simple greedy agglomeration algorithm achieves ratio of 2 for SSP. Here, we present a novel approach to bound the superstring approximation ratio with the compression ratio, which leads to a first proof of the greedy conjecture for 3-SSP.
Type de document :
Rapport
[Research Report] RR-14009, LIRMM. 2014
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01070596
Contributeur : Eric Rivals <>
Soumis le : mercredi 1 octobre 2014 - 17:36:35
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 14 avril 2017 - 14:08:02

Fichier

approx-kSCS-RR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01070596, version 1

Collections

Citation

Bastien Cazaux, Eric Rivals. 3-Shortest Superstring is 2-approximable by a greedy algorithm. [Research Report] RR-14009, LIRMM. 2014. 〈lirmm-01070596〉

Partager

Métriques

Consultations de la notice

1409

Téléchargements de fichiers

360