12 ago 2020
14:00 Defesa de Mestrado Integralmente a distância
Tema
Approximation Algorithms for Routing and Connectivity Problems with Multiple Distance Functions.
Aluno
Greis Yvet Oropeza Quesquén
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve resumo
Nesta dissertação, estudamos algumas generalizações de problemas clássicos de roteamento e conectividade cujas instâncias são compostas por um grafo completo e múltiplas funções de distância.
Um exemplo desse tipo de problema é o Problema do Caixeiro Alugador (CaRS), no qual um viageiro deseja visitar um conjunto de cidades alugando um ou mais carros disponíveis. Cada carro tem uma função de custo e uma taxa de retorno ao local do aluguel. CaRS é uma generalização do Problema do Caixeiro Viajante (TSP).
Nós lidamos com esses problemas usando algoritmos de aproximação, que são algoritmos eficientes que produzem soluções com garantia de qualidade. Neste trabalho, são apresentadas duas abordagens, uma baseada em uma redução linear que preserva o fator de aproximação e outra baseada na construção de instâncias de dois problemas distintos.
Os problemas considerados são o Steiner TSP, o Problema do Passeio com Coleta de Prêmios e o Problema da Floresta Restrita. Generalizamos cada um desses problemas considerando múltiplas funções de distância e, para cada um deles, apresentamos um algoritmo de aproximação com fator O(log n). Essas aproximações são assintoticamente ótimas, já que também observamos que não há algoritmos com fator o(log n), a não ser que P = NP.
Banca examinadora
Titulares:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Carla Negri Lintzmayer | CMCC/UFABC |
| Pedro Jussieu de Rezende | IC/UNICAMP |
Suplentes:
| Zanoni Dias | IC/UNICAMP |
| Mário César San Felice | DC/UFSCar |