Uma Aproximação Ótima para o Problema do Caixeiro Alugador - Pedrosa, Lehilton L. C.; Schouery, Rafael C. S. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2018.3146, 2018)
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 veículos. Cada veículo tem uma função de distância distinta, mas para cada veí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.