Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings

Bastien Cazaux 1 Eric Rivals 2, 1
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Covering a directed graph by a Hamiltonian path or a set of words by a superstring belong to well studied optimisation problems that prove difficult to approx-imate. Indeed, the Maximum Asymmetric Travelling Salesman Problem (Max-ATSP), which asks for a Hamiltonian path of maximum weight covering a digraph, and the Shortest Superstring Problem (SSP), which, for a finite language P := {s 1 , . . . , s p }, searches for a string of minimal length having each input word as a substring, are both Max-SNP hard. Finding a short superstring requires to choose a permutation of words and the associated overlaps to minimise the superstring length or to maximise the compression of P . Hence, a strong relation exists between Max-ATSP and SSP since solving Max-ATSP on the Overlap Graph for P gives a shortest superstring. Numerous works have designed algorithms that improve the approximation ratio but are increasingly complex. Often, these rely on solving the pendant problems where the cover is made of cycles instead of single path (Max-CC and SCCS). Finally, the greedy algorithm remains an attractive solution for its simplicity and ease of implementation. Its approximation ratios have been obtained by different approaches. In a seminal but complex proof, Tarhio and Ukkonen showed that it achieves 1/2 compression ratio for Max-CC. Here, using the full power of subset systems, we provide a unified approach for proving simply the approximation ratio of a greedy algorithm for these four prob-lems. Especially, our proof for Maximal Compression shows that the Monge property suffices to derive the 1/2 tight bound.
Type de document :
Communication dans un congrès
Jan Holub; Jan Zd’arek. PSC'2014: Prague Stringology Conference, Sep 2014, Prague, Czech Republic. Czech Technical University in Prague, Czech Republic, ISBN 978-80-01-05547-2, pp.148-161, 2014, Proceedings of the Prague Stringology Conference 2014. 〈http://www.stringology.org/event/2014/p14.html〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01100683
Contributeur : Eric Rivals <>
Soumis le : mardi 6 janvier 2015 - 18:27:47
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 3 juin 2015 - 17:32:54

Fichier

PSC2014_article14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01100683, version 1

Collections

Citation

Bastien Cazaux, Eric Rivals. Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings. Jan Holub; Jan Zd’arek. PSC'2014: Prague Stringology Conference, Sep 2014, Prague, Czech Republic. Czech Technical University in Prague, Czech Republic, ISBN 978-80-01-05547-2, pp.148-161, 2014, Proceedings of the Prague Stringology Conference 2014. 〈http://www.stringology.org/event/2014/p14.html〉. 〈lirmm-01100683〉

Partager

Métriques

Consultations de la notice

356

Téléchargements de fichiers

368