Defesa de Dissertação de Mestrado de Osniel Lopes Teixeira, 02/09/25, 14h, por videoconferência
Link para defesa: https://meet.google.com/ojn-xzyw-uha
Graph-Based Reinforcement Learning for Combinatorial Optimization: Applications to Dominating Set and Vertex Cover
Resumo:
Este trabalho aplica Deep Q-Learning para aproximar soluções para os problemas NP-Difíceis Cobertura Mínima de Vértices e Conjunto Dominante Mínimo, formulando-os como tarefas de Aprendizado por Reforço, onde um agente aprende a construir soluções de maneira sequencial. Além de um modelo de DQL puro, também foi testado um modelo que combina busca local para refinar os resultados. Além disso, foram desenvolvidos e analisados atributos indicativos do potencial dos nós para a construção de soluções.
Abstract:
This work applies Deep Q-Learning to approximate solutions for the NP-hard Minimum
Vertex Cover and Minimum Dominating Set problems, framing them as Reinforcement
Learning tasks, where an agent learns how to construct solutions step-by-step. Beyond
the pure DQL, it was also tested a model that combines a local search procedure to refine the results. Furthermore, it was developed and analyzed attributes that indicate the potential of nodes for the construction of solutions.
Banca examinadora:
Prof. Fábio Protti, UFF – Presidente
Profa. Aline Marins Paes Carvalho, UFF
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Daniel Ratton Figueiredo, UFRJ
Dr. Felipe Maia Galvão França, Google