Data: 28/05/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Algoritmo de aproximação assintoticamente ótimo para o problema do alugador de veículos
Palestrante: Lehilton Lelis Chaves Pedrosa (Unicamp)


Resumo: No problema clássico do caixeiro viajante (TSP), é necessário encontrar uma rota que visite um conjunto de $n$ cidades, de modo que a distância total percorrida seja mínima. Uma generalização considerada é o CARS (Traveling Car Renter Problem), para o qual a rota é percorrida alugando-se um conjunto de carros e o custo para viajar entre duas cidades depende do carro usado. O locatário do carro pode optar por trocar de veículo em qualquer cidade, mas para isso deve pagar uma taxa para devolver o carro ao local de retirada. Esse problema aparece tanto na logística e no transporte urbano, quando os veículos podem ser fornecidos por várias empresas, como no setor de turismo. Consideramos o caso em que a taxa de retorno é um número fixo $g \ge 0$, que chamamos de Uniform CARS. Mostramos que, já para essa versão, não existe um algoritmo de aproximação com fator $o(\log n)$ a menos que P = NP. A principal contribuição é uma $O(\log n)$-aproximação para o problema, que é baseado no arredondamento aleatorizado de uma relaxação de PL de tamanho exponencial.

Ref: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=11426