Algoritmos de aproximação e parametrizados para problemas de conectividade de pares

Resumo

Os problemas de conectividade de pares formam uma vertente dos problemas de localização, em que devemos posicionar estruturas de forma a satisfazer restrições de conexão entre pares de pontos de rede. Diversos problemas de interesse prático podem ser assim classificados, como o problema da localização e alocação de terminais (HLP), em que temos que atender demandas entre pares de clientes através de terminais de uma rede, com todo o fluxo de produtos passando por eles. Com variantes desse problema, podemos modelar aplicações em setores de transporte aéreo, distribuição de produtos e transporte público. Neste projeto, estamos interessados em estudar problemas de conectividade de pares levando em conta suas principais variantes e parâmetros. Iremos desenvolver algoritmos de aproximação e algoritmos parametrizados, assim como resultados de inaproximabilidade e de dificuldade associados. Este trabalho irá lidar com uma grande combinação de problemas e técnicas algorítmicas, particularmente aquelas que correspondem a questões em aberto, apesar do grande número de trabalhos e referências sobre esses e outros problemas de localização. Por exemplo, enquanto existem algoritmos de aproximação para alguns casos do HLP, desenvolvidos pelo candidato durante seu mestrado, não são conhecidas aproximações para diversas outras variantes, nem há trabalhos que o estudam sob o ponto de vista de complexidade parametrizada. Além disso, esperamos investigar algoritmos de aproximação parametrizados, uma área recente da literatura que une as duas abordagens a fim de tratar problemas que são difíceis para cada uma separadamente, constituindo assim uma boa oportunidade de realizar pesquisa inovadora. (AU)