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

• Processo: 18/00910-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2018
• Situação: Interrompido
• Área de 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
• Palavra(s)-Chave do Pesquisador: algoritmo de aproximação | alocação de terminais | problema min-max | restrição de capacidade | 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)