Approximation and parameterized algorithms for pair connectivity problems

Autor(es)

Marcelo Pinheiro Leite Benedito

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2023-08-16

Membros da banca

Lehilton Lelis Chaves Pedrosa; Uéverton dos Santos Souza; Mário César San Felice; Santiago Valdés Ravelo; Orlando Lee

• Orientador: Lehilton Lelis Chaves Pedrosa

Resumo

Nesta tese, tratamos de problemas de conectividade de pares em grafos, cuja entrada inclui um conjunto de pares de vértices, chamados de demandas, e uma solução consiste de alguma estrutura conectando as demandas. Estudamos os problemas do ponto de vista de algoritmos de aproximação e parametrizados, que são combinados para superar barreiras advindas do uso de cada estratégia separadamente. Os resultados utilizam tanto técnicas existentes, como programação dinâmica sobre decomposição em árvores, como novas técnicas que podem ser generalizadas para problemas relacionados. No Star k-Hub Center (SkHC), recebemos um grafo com um vértice central e um inteiro k e a tarefa é selecionar k vértices, chamados de terminais, e atribuir cada vértice a um terminal. O objetivo é minimizar o comprimento do maior caminho que conecta cada par de vértices e passa pelo centro e terminais atribuídos. Iniciamos o estudo do SkHC na área de complexidade parametrizada, derivando os primeiros resultados de dificuldade em parâmetros estruturais e apresentando um algoritmo de aproximação parametrizado pela treewidth, isto é, um algoritmo que executa em tempo O^*((tw/?)^O(tw)) e produz uma solução com fator 1 + ? do valor ótimo. No Multiple Allocation k-Hub Center (MAkHC), recebemos um grafo cujos vértices são clientes ou terminais, um conjunto de demandas composto por pares de clientes e um inteiro k. O objetivo é selecionar k terminais, minimizando o maior caminho que conecta os vértices de uma demanda passando pelo terminal associado. Também damos início ao estudo deste problema sob as lentes de complexidade parametrizada, fornecendo limitantes inferiores de aproximação e uma redução que elimina a possibilidade de existência de algoritmos com outros parâmetros. O resultado principal para o MAkHC é uma (2 + ?)-aproximação parametrizada pela treewidth, usando técnicas que removem a dependência de outros parâmetros e lidam com o conjunto de demandas arbitrário. No Spanning Tree-Star (STS), temos um grafo com duas funções de custos nas arestas e uma solução é um subgrafo conexo gerador. O objetivo é minimizar a soma dos custos das arestas da solução, onde arestas pendantes e não pendantes são precificadas distintamente. Também consideramos variantes do STS em que as arestas não pendantes induzam um caminho ou um ciclo. Apresentamos algoritmos para o STS e variantes, parametrizados por treewidth ou pathwidth, que executam em tempo com expoente simples. Estes resultados usam rank-based approach e aplicam uma nova modelagem de rótulos (AU)

• Processo FAPESP: 19/10400-2 - Algoritmos de aproximação e parametrizados para problemas de conectividade de pares
• Beneficiário: Marcelo Pinheiro Leite Benedito
• Modalidade de apoio: Bolsas no Brasil - Doutorado