19 nov 2021
14:00 Defesa de Doutorado Integralmente a distância
Tema
Algoritmos de Aproximação para Problemas de Rede com Restrições de Vértices
Aluno
Hugo Kooki Kasuya Rosado
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve resumo
No Problema da Árvore 34 de Steiner (ST) clássico, a entrada é composta por um grafo com pesos não negativos nas arestas e um conjunto de vértices chamados terminais. O objetivo é encontrar uma árvore conectando todos os terminais cuja soma dos pesos das arestas seja mínima. Esta tese apresenta algoritmos de aproximação para ST e variantes NP-difíceis em que há custos adicionais associados aos vértices. Os algoritmos são baseados tanto em técnicas conhecidas, quanto técnicas novas cujo desenvolvimento aprofunda o entendimento desses e de outros problemas relacionados.
O Problema da Árvore de Steiner k-restrita (k-RST) é uma variante utilizada por algoritmos de aproximação para ST. Nessa variante, a solução é obtida pela união de árvores cuja folhas são todas terminais e possuem, cada uma, no máximo k terminais. Neste trabalho, apresentamos uma nova formulação relaxada baseada em programação linear e demonstramos que ela é pelo menos tão forte quanto a relaxação tradicional baseada em cortes de componentes direcionadas. Essa nova formulação tem uma interpretação geométrica que pode ser usada como ferramenta alternativa para novos algoritmos. Em particular, apresentamos um algoritmo primal-dual com fator de aproximação 1,28 para o caso em que há uma aresta de peso 1 ou 2 entre todo par de vértices.
No Problema do Cabo-Trincheira de Steiner (SCT), uma entrada contém também um vértice especial, que representa um servidor. Uma solução é uma árvore conectando os terminais em que cada aresta representa uma trincheira a ser construída para a passagem de cabos que ligam cada um dos terminais ao servidor. O custo de uma trincheira é proporcional ao peso de sua aresta correspondente na árvore e o custo de um cabo é proporcional ao peso do caminho correspondente na árvore. O objetivo é encontrar uma solução que minimize o custo total de preparar trincheiras e de ligar cabos. Nesta tese, apresentamos um algoritmo de aproximação com fator 2,88 + ε. Além disso, demostramos que mesmo o caso particular em que todos os vértices são terminais é NP-difícil, corrigindo uma demonstração anterior na literatura. Mais do que isso, mostramos que é NP-difícil obter uma aproximação para esse caso com fator menor do que 1,000475.
No Problema da Árvore de Steiner k-Coletora de Prêmios (k-PCST), ao invés de um conjunto de terminais, cada vértice da entrada é associado a um número não negativo, representando uma penalidade. O objetivo é encontrar uma árvore com pelo menos k vértices que minimize o peso total das arestas na árvore mais as penalidades dos vértices não incluídos na árvore. Esta tese apresenta uma 2-aproximação baseada em uma nova técnica para o controle de execução de um algoritmo clássico primal-dual para ST. Nosso algoritmo supera os resultados anteriores, melhorando tanto o fator de aproximação, quanto o tempo de execução.
Banca examinadora
Titulares:
| 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 |
Suplentes:
| Eduardo Candido Xavier | IC/UNICAMP |
| Christiane Neme Campos | IC/UNICAMP |
| José Coelho de Pina Junior | IME/USP |