16 ago 2023
13:30 Defesa de Doutorado Sala 85 do IC
Tema
Algoritmos de Aproximação e Parametrizados para Problemas de Conectividade de Pares
Aluno
Marcelo Pinheiro Leite Benedito
Orientador / Docente
Lehilton Lelis Chaves Pedrosa
Breve resumo
Nesta tese, tratamos de problemas de conectividade de pares na interseção de algoritmos de aproximação e parametrizados. Estas técnicas geralmente são usadas de forma conjunta quando nenhuma delas sozinha é capaz de obter resultados satisfatórios, quando pesquisadores querem resolver conjuntos específicos de instâncias ou obter um melhor entendimento da dificuldade de um problema. Nossos resultados aplicam programação dinâmica sobre uma decomposição em árvore, usando técnicas existentes e introduzindo outras. No Star k-Hub Center (SkHC), temos como entrada um grafo com um vértice central e um inteiro k, e o objetivo é selecionar k terminais e atribuir cada vértice a exatamente um terminal, minimizando o maior comprimento de um caminho entre dois vértices. Iniciamos o estudo do SkHC na área de complexidade parametrizada, com resultados de dificuldade em parâmetros estruturais de grafos e um algoritmo parametrizado pela treewidth do grafo, que produz uma solução com fator (1 + ε) do valor ótimo, ou prova que não existe tal solução. No Multiple Allocation k-Hub Center (MAkHC), temos como entrada um grafo cujos vértices são clientes ou terminais, um conjunto de demandas composto por pares de clientes e um inteiro k, e o objetivo é selecionar k terminais tal que o custo do maior caminho de uma demanda seja minimizado. Também damos início ao estudo deste problema sob as lentes de complexidade parametrizada, com limitantes inferiores de aproximação e uma redução que elimina a possibilidade de algoritmos parametrizados por highway dimension, pathwidth e outros. O resultado principal para o MAkHC é uma (2 + ε)-aproximação parametrizada pela treewidth do grafo, usando técnicas que removem a dependência de outros parâmetros e lidam com o conjunto de demandas genérico. No Spanning Tree-Star (STS), temos um grafo com duas funções de custos nas arestas, e o objetivo é encontrar um subgrafo gerador conexo de menor custo, onde vértices internos induzam uma árvore. O custo de uma solução é a soma dos custos das arestas, onde uma aresta é precificada dependendo se suas extremidades são vértices internos. Também são consideradas variantes onde os vértices internos induzam um caminho ou um ciclo. Apresentamos algoritmos para o STS e variantes, parametrizados por treewidth ou pathwidth, executando em tempo com expoente único. Estes resultados usam rank-based approach e aplicam nossa modelagem de rótulos.
Banca examinadora
Titulares:
| Lehilton Lelis Chaves Pedrosa | IC/UNICAMP |
| Orlando Lee | IC/UNICAMP |
| Uéverton dos Santos Souza | IC/UFF |
| Mário César San Felice | DC/UFSCar |
| Santiago Valdés Ravelo | INF/UFRGS |
Suplentes:
| Pedro Jussieu de Rezende | IC/UNICAMP |
| Cristina Gomes Fernandes | IME/USP |
| Maycon Sambinelli | CMCC/UFABC |