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

详细信息    查看全文

• 作者：Bastien Cazaux ^{bastien.cazaux@lirmm.fr" class="auth_mail" title="E-mail the corresponding author} ; Eric Rivals ; ^{rivals@lirmm.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Approximation algorithm ; Shortest Superstring Problem ; Stringology ; Data compression ; Assembly ; Greedy conjecture
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 October 2016
• 年：2016
• 卷：212
• 期：Complete
• 页码：48-60
• 全文大小：529 K

文摘

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₁,…,s_p}$P≔\{s_1,\dots ,s_p\}$, asks for w$w$, a superstring of P$P$ minimising ∑_si∈S|s_i|−|w|${\sum }_{s_i\in S}\left|s_i\right|-\left|w\right|$, are both difficult to approximate (Max-SNP hard). Solving Max-ATSP on the overlap graph of the words of P$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.