Uma Aproximação Ótima para o Problema do Caixeiro Alugador⇤

  • Lehilton L. C. Pedrosa
  • Rafael C. S. Schouery

Resumo


No clássico Problema do Caixeiro Viajante (TSP), queremos encontrar uma rota que passa por um conjunto de n cidades e que minimize a dist ância total percorrida. Uma generalização conhecida é o chamada Problema do Caixeiro Alugador, em que a rota pode ser percorrida alugando-se um subconjunto de véıculos. Cada véıculo tem uma função de dist ância distinta, mas para cada véıculo alugado, paga-se uma taxa de retorno g 0. O objetivo é minimizar a soma das dist âncias percorridas mais as taxas de retorno. Neste trabalho, apresentamos uma O(log n)-aproximação para o problema. Esse algoritmo é assintoticamente ótimo já que também mostramos que n ão há aproximação com fator o(log n), a n ão ser que P = NP.

Publicado
26/07/2018
PEDROSA, Lehilton L. C.; SCHOUERY, Rafael C. S.. Uma Aproximação Ótima para o Problema do Caixeiro Alugador⇤. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3146.