Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

On Alternative Approaches for Approximating the Transposition Distance

Autor(es):
Galvao, Gustavo Rodrigues [1] ; Dias, Zanoni [1]
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
Linha de fomento: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs