HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings

Bastien Cazaux 1, 2 Eric Rivals 1, 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The Maximum Asymmetric Travelling Salesman Problem (Max-ATSP), which asks for a Hamiltonian path of maximum weight covering a digraph, and the Maximum Compression(Max-Comp), which, for a finite language P≔{s_1,…,s_p}, asks for w, a superstring of P minimising ∑s_i ∈S |s_i|−|w|, are both difficult to approximate (Max-SNP hard). Solving Max-ATSP on the overlap graph of the words of P solves Max-Comp. Many approximate algorithms have been designed to improve their approximation ratios, but these 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). Thus, the greedy algorithm remains an attractive solution for its simplicity and ease of implementation. Here, using the full power of subset systems, we provide a unified approach for proving simply the approximation ratios of a greedy algorithm for these four problems. In addition, we introduce two new problems dealing with the case of cyclic input words, and exhibit a greedy approximation ratio for them. The Maximum Partitioned Hamiltonian Path generalises the Maximum Asymmetric Travelling Salesman Problem when the nodes are partitioned into classes and the path must contain one element of each class. The Maximum Cyclic Compression is the natural counterpart of Maximum Compression for cyclic strings.
Complete list of metadata

Contributor : Eric Rivals Connect in order to contact the contributor
Submitted on : Friday, March 11, 2016 - 3:33:50 PM
Last modification on : Wednesday, November 3, 2021 - 7:44:50 AM

Links full text




Bastien Cazaux, Eric Rivals. The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings. Discrete Applied Mathematics, Elsevier, 2016, 212, pp.48-60. ⟨10.1016/j.dam.2015.06.003⟩. ⟨lirmm-01286943⟩



Record views