19 Nov 2021
14:00 Doctoral defense Fully distance
Theme
Approximation Algorithms for Network Problems with Vertex Constraints
Student
Hugo Kooki Kasuya Rosado
Advisor / Teacher
Lehilton Lelis Chaves Pedrosa
Brief summary
In the classic Steiner's Tree Problem 34 (ST), the input is composed of a graph with non-negative edge weights and a set of vertices called terminals. The objective is to find a tree connecting all terminals whose sum of edge weights is minimal. This thesis presents approximation algorithms for ST and NP-hard variants in which there are additional costs associated with the vertices. Algorithms are based on both known and new techniques whose development deepens the understanding of these and other related problems. The k-restricted Steiner Tree Problem (k-RST) is a variant used by approximation algorithms for ST. In this variant, the solution is obtained by joining trees whose leaves are all terminals and each one has at most k terminals. In this work, we present a new relaxed formulation based on linear programming and demonstrate that it is at least as strong as the traditional relaxation based on directed component cuts. This new formulation has a geometric interpretation that can be used as an alternative tool for new algorithms. In particular, we present a primal-dual algorithm with an approximation factor of 1,28 for the case where there is an edge with a weight of 1 or 2 between every pair of vertices. In Steiner's Cable-Trench Problem (SCT), an entry also contains a special vertex, which represents a server. One solution is a tree connecting the terminals where each edge represents a trench to be built for the passage of cables connecting each terminal to the server. The cost of a trench is proportional to the weight of its corresponding edge in the tree and the cost of a cable is proportional to the weight of the corresponding path in the tree. The goal is to find a solution that minimizes the total cost of preparing trenches and connecting cables. In this thesis, we present an approximation algorithm with a factor of 2,88 + ε. Furthermore, we demonstrate that even the particular case where all vertices are terminal is NP-hard, correcting a previous demonstration in the literature. More than that, we show that it is NP-hard to get an approximation for this case with a factor smaller than 1,000475. In the k-Premium Collector Steiner Tree Problem (k-PCST), instead of a set of terminals, each vertex of the input is associated with a non-negative number, representing a penalty. The goal is to find a tree with at least k vertices that minimizes the total weight of the edges in the tree plus the penalties of the vertices not included in the tree. This thesis presents a 2-approximation based on a new technique to control the execution of a classical primal-dual algorithm for ST. Our algorithm surpasses the previous results, improving both the approximation factor and the execution time.
Examination Board
Headlines:
| Lehilton Lelis Chaves Pedrosa | IC / UNICAMP |
| Cristina Gomes Fernandes | IME / USP |
| Fábio Protti | IC / UFF |
| Flávio Keidi Miyazawa | IC / UNICAMP |
| Ricardo Dahab | IC / UNICAMP |
Substitutes:
| Eduardo Candido Xavier | IC / UNICAMP |
| Christiane Neme Campos | IC / UNICAMP |
| José Coelho de Pina Junior | IME / USP |