12 August 2020
14:00 Master's Defense Fully distance
Theme
Approximation Algorithms for Routing and Connectivity Problems with Multiple Distance Functions.
Student
Greis Yvet Oropeza Quesquén
Advisor / Teacher
Lehilton Lelis Chaves Pedrosa
Brief summary
In this dissertation, we study some generalizations of classical routing and connectivity problems whose instances are composed of a complete graph and multiple distance functions. An example of this type of problem is the Renting Clerk Problem (CaRS), in which a traveler wants to visit a group of cities by renting one or more available cars. Each car has a cost function and a rate of return to the rental location. CaRS is a generalization of the Traveling Salesman Problem (TSP). We address these problems using approximation algorithms, which are efficient algorithms that produce quality-assured solutions. In this work, two approaches are presented, one based on a linear reduction that preserves the approximation factor and another based on the construction of instances of two different problems. The problems considered are the Steiner TSP, the Tour with Prize Collection Problem and the Restricted Forest Problem. We generalize each of these problems considering multiple distance functions and, for each of them, we present an approximation algorithm with an O(log n) factor. These approximations are asymptotically optimal, as we also observe that there are no algorithms with an o(log n) factor, unless P = NP.
Examination Board
Headlines:
Lehilton Lelis Chaves Pedrosa IC / UNICAMP
Carla Negri Lintzmayer CMCC / UFABC
Pedro Jussieu de Rezende IC / UNICAMP
Substitutes:
Zanoni Dias IC / UNICAMP
Mário César San Felice DC / UFSCar