Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Tuesday, January 6, 2015 - 6:27:47 PM
Last modification on : Friday, August 5, 2022 - 3:02:17 PM
Long-term archiving on: : Wednesday, June 3, 2015 - 5:32:54 PM


Files produced by the author(s)


  • HAL Id : lirmm-01100683, version 1



Bastien Cazaux, Eric Rivals. Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings. PSC: Prague Stringology Conference, Czech Technical University in Prague, Sep 2014, Prague, Czech Republic. pp.148-161. ⟨lirmm-01100683⟩



Record views


Files downloads