Relationship between superstring and compression measures: New insights on the greedy conjecture - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2018

Relationship between superstring and compression measures: New insights on the greedy conjecture

Résumé

A superstring of a set of words is a string that contains each input word as a substring. Given such a set, the Shortest Superstring Problem (SSP) asks for a superstring 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 algorithm achieves ratio of 2 for SSP. Here, we present a novel approach to bound the superstring approximation ratio with the compression ratio, which, when applied to the greedy algorithm, shows a 2 approximation ratio for 3-SSP, and also that greedy achieves ratios smaller than 2. This leads to a new version of the greedy conjecture.
Fichier principal
Vignette du fichier
Cazaux-Rivals-DAM-2018.pdf (423.2 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-01800340 , version 1 (25-05-2018)

Licence

Paternité

Identifiants

Citer

Bastien Cazaux, Eric Rivals. Relationship between superstring and compression measures: New insights on the greedy conjecture. Discrete Applied Mathematics, 2018, 245, pp.59-64. ⟨10.1016/j.dam.2017.04.017⟩. ⟨lirmm-01800340⟩
560 Consultations
335 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More