Busca avançada
Ano de início
Entree

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

Processo: 19/10400-2
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de fevereiro de 2020
Vigência (Término): 31 de dezembro de 2022
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Lehilton Lelis Chaves Pedrosa
Beneficiário:Marcelo Pinheiro Leite Benedito
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Vinculado ao auxílio:15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
Assunto(s):Algoritmos de aproximação   Problemas de localização de facilidades   Conectividade

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)