Algoritmos Aproximativos para o Problema do Caixeiro Viajante
Autores
|
1805 |
Andrea Rosário Pari Soto
|
44,413,769
|
|
1806 |
44,413,769
|
|
|
1807 |
44,413,769
|
Informações:
Publicações do PESC
Este trabalho consiste no estudo de algoritmos aproximativos para o problema do caixeiro viajante euclideano para a obtenção de um tour ótimo para grafos não direcionados. Apresenta-se também um esquema aproximativo desenvolvido recentemente por Sanjeev Arora para o problema do caixeiro viajante euclideano no plano. A idéia principal desse esquema é realizar um particionamento geométrico recursivo de uma instância em instâncias menores e posteriormente aplicar a técnica de programação dinâmica.
In this work we study approximation algorithms for the Euclidean Traveling Salesman Problem. We also present an aproximation scheme for the Traveling Salesman Problem for the plane, that was recently developed by Sanjeev Arora. The key idea of this scheme is to realize a recursive geometric partition of an instance into smaller instances and then to apply Dinamic Programing.