Details

Autor(en) / Beteiligte

• Cazaux, Bastien
• Rivals, Eric

Titel

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

Ist Teil von

• Discrete Applied Mathematics, 2016-10, Vol.212, p.48-60

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2016

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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≔{s1,…,sp}, asks for w, a superstring of P minimising ∑si∈S|si|−|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.