Algoritmos de aproximação para o problema da localização de instalações
Algoritmos de aproximação e online competitivos para problemas de escalonamento
Abordagens Teóricas e Práticas para Problemas de Empacotamento
| Processo: | 17/11382-2 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de setembro de 2017 |
| Data de Término da vigência: | 07 de fevereiro de 2018 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Cristina Gomes Fernandes |
| Beneficiário: | Mário César San Felice |
| Instituição Sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Vinculado ao auxílio: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM |
| Assunto(s): | Algoritmos de aproximação Otimização combinatória |
| Palavra(s)-Chave do Pesquisador: | Algoritmos de Aproximação | Computação online | Localização de Instalações | Projeto de Redes | Otimização Combinatória |
Resumo Este é o projeto de pesquisa do pós-doutorado de Mário César San Felice, a ser realizado no Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP), de 01/08/2017 a 31/07/2019, sob a supervisão da Profa. Dra. Cristina Gomes Fernandes. O objetivo deste é abordar problemas de otimização combinatória, visando o desenvolvimento e análise de novos algoritmos, o refinamento da análise de algoritmos existentes, e a obtenção de melhores cotas inferiores para os problemas. O foco do projeto são problemas de clusterização, nos quais temos que agrupar objetos por algum critério de similaridade, e problemas de projeto de redes, nos quais temos que construir uma infraestrutura para atender às demandas de conectividade da entrada. Temos um interesse especial por problemas de projeto de redes com duas camadas, que surgem quando temos a opção de construir dois níveis de infraestrutura com diferentes custos e capacidades para atender uma certa demanda de transporte ou transmissão de dados. O problema central de projeto de redes com duas camadas é o problema de localização de instalações conectadas, que combina características dos problemas clássicos da árvore de Steiner e de localização de instalações com o modelo rent-or-buy. Pretendemos abordar estes problemas tanto no modelo de computação offline como online utilizando, respectivamente, as abordagens de algoritmos de aproximação e de análise competitiva. | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |