Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover of Strings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Reports Year : 2013

Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover of Strings

Abstract

Given a directed graph G with weights on its arcs, the Maximum Asymmetric Travelling Salesman Problem (Max- ATSP) asks for a Hamiltonian path of maximum weight covering G. Max-ATSP, a central problem in computer science, is known to NP-hard and hard to approximate. In the general case, when the Triangle Inequality is not satisfied, the best approximation ratio known to date equals 2/3. Now consider the Overlap Graph for a set of finite words P := {s1 , . . . , s p }: the directed graph in which an arc links two words with a weight equals to the length of their maximal overlap. When Max-ATSP is applied to the Overlap Graph, it solves the Maximal Compression or Shortest Superstring problem, where one searches for a string of minimal length having each input word as a substring. Again these problems are hard to approximate. Both for Max-ATSP and for Maximal Compression, good approximation algorithms use a cover of the graph by a set of cycles or of the words by a set of cyclic strings. These questions are known as Maximal Directed Cyclic Cover (MDCC) and as Shortest Cyclic Cover of Strings (SCCS), and can be solved in polynomial time. However, among these four problems, the approximation ratio achieved by a simple greedy algorithm is known only for Maximal Compression. In a seminal but complex proof, Tarhio and Ukkonen showed that it achieves 1/2 compression ratio. Taking advantage of the power of subset systems, we investigate the approximation of associated greedy algorithms for these four problems, and show they reach a ratio of 1/3 for Max- ATSP, 1/2 for Maximal Compression and for Maximal Cyclic Cover, and gives an exact solution for the Shortest Cyclic Cover of Strings. The proof for Maximal Compression is simpler than known ones. For these problems, greedy algorithms are easier to implement and often faster than existing approximation algorithms, an important fact since these problems have practical applications, for instance in data compression and computational biology.
Fichier principal
Vignette du fichier
Compression-cover-greedy-RR.pdf (142.83 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00932660 , version 1 (17-01-2014)

Identifiers

  • HAL Id : lirmm-00932660 , version 1
  • PRODINRA : 314729

Cite

Bastien Cazaux, Eric Rivals. Approximation of greedy algorithms for Max-ATSP, Maximal Compression, and Shortest Cyclic Cover of Strings. RR-14001, 2013, pp.12. ⟨lirmm-00932660⟩
764 View
374 Download

Share

More