Heurística quase-linear para resolver o problema do caixeiro viajante euclidiano com baixa diferença

O problema do caixeiro viajante (TSP) é um problema de otimização NP-difícil bem estudado. Apresentamos uma nova heurística para encontrar soluções aproximadas para o caso do TSP com métrica euclidiana. Nosso algoritmo de par-central roda em tempo quase-linear e em espaço linear. Em experimentos práticos em uma variedade de benchmarks bem conhecidos, o algoritmo mostra um tempo de execução linearítmico (ou seja, O(nlogn)). As soluções encontradas pelo algoritmo de par-central são muito boas em instâncias de problemas menores, e melhores do que aquelas geradas por qualquer outra heurística com tempo de execução no máximo quadrático. Eventualmente, a diferença média do algoritmo de par-central em todas as instâncias de benchmark com menos de 1.001 pontos é de 0,94% e para todas as instâncias com mais de 1.000 pontos até 100 milhões de pontos é de 4,57%.