Autores

1805
Andrea Rosário Pari Soto
44,413,769
1806
44,413,769
1807
44,413,769

Informações:

Publicações do PESC

Título
Algoritmos Aproximativos para o Problema do Caixeiro Viajante
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
27/10/1999
Resumo

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.

Abstract

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.

Arquivo
Topo