Busca avançada
Ano de início
Entree

Algoritmos para problemas Min-Max de alocação de p-Terminais e variantes

Processo: 18/00910-0
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2018
Situação:Interrompido
Á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:Vinícius Balbino de Souza
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

Resumo

Em diversas aplicações das indústrias de transportes, logística, sistemas de telecomunicações, serviços postais e redes de distribuição, necessitamos a instalação de terminais, como aeroportos de conexão ou switches de rede. Um terminal é um centro de consolidação, troca e ordenação, que permite remanejamento de conexões diretas, usando uma quantidade menor de ligações indiretas. Neste projeto, estudaremos o problema de alocação de terminais e variantes. Um exemplo é o chamado problema dos p-terminais (p-hub center problem), que consiste em determinar p pontos de uma rede a fim de servir demandas por fluxo entre pares de nós da rede e minimizado o maior custo entre origem e destino. Muitos desses problemas são NP-difíceis e, portanto, examinaremos principalmente os algoritmos de aproximação. Estudaremos os algoritmos e técnicas existentes, buscando novos algoritmos para variantes ou casos particulares, realizando o estudo de sua complexidade e dando garantias de aproximação, sempre que possível. Em particular, estudaremos a versão do problema dos p-terminais com capacidades rígidas, i.e., quando um terminal em uma dada localização pode servir um número máximo de clientes. (AU)