| Autor(es): |
Número total de Autores: 2
|
| Afiliação do(s) autor(es): | [1] Univ Estadual Campinas, Campinas, SP - Brazil
Número total de Afiliações: 1
|
| Tipo de documento: | Artigo Científico |
| Fonte: | JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 20, n. 9, p. 1259-1283, 2014. |
| Citações Web of Science: | 0 |
| Resumo | |
We study the problem of sorting by transpositions, which consists in computing the minimum number of transpositions required to sort a permutation. This problem is NP-hard and the best approximation algorithms for solving it are based on a standard tool for attacking problems of this kind, the cycle graph. In an attempt to bypass it, some researches posed alternative approaches. In this paper, we address three algorithms yielded by such approaches: a 2.25-approximation algorithm based on breakpoint diagrams, a 3-approximation algorithm based on permutation codes, and a heuristic based on longest increasing subsequences. Regarding the 2.25-approximation algorithm, we show that previous experimental data on its approximation ratio are incorrect. Regarding the 3-approximation algorithm, we close a missing gap on the proof of its approximation ratio and we show a way to run it in O(n log n) time. Regarding the heuristic, we propose a minor adaptation that allow us to prove an approximation bound of 3. We present experimental data obtained by running these algorithms for all permutations with up to 13 elements and by running these algorithms and the best known algorithms based on the cycle graph for large permutations. The data indicate that the 2.25-approximation algorithm is the best of the algorithms based on alternative approaches and that it is the only one comparable to the algorithms based on the cycle graph. (AU) | |
| Processo FAPESP: | 13/08293-7 - CECC - Centro de Engenharia e Ciências Computacionais |
| Beneficiário: | Munir Salomao Skaf |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |