| Processo: | 14/14209-1 |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Data de Início da vigência: | 01 de novembro de 2014 |
| Data de Término da vigência: | 31 de julho de 2015 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Acordo de Cooperação: | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) |
| Pesquisador responsável: | Cristina Gomes Fernandes |
| Beneficiário: | Lehilton Lelis Chaves Pedrosa |
| 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 Programação linear |
| Palavra(s)-Chave do Pesquisador: | Algoritmos de Aproximação | k-centros | k-medianas | Localização de Instalações | programação linear | Algoritmos de Aproximação |
Resumo O objetivo deste projeto de pós-doutoramento é estudar e obter algoritmos de aproximação ou resultados de inaproximabilidade para problemas de otimização combinatória, particularmente para diversos problemas de projeto de rede com restrições mais realistas. Os problemas clássicos de rede, como k-centros, k-medianas e localização de instalações, têm uma vasta lista de aplicações, como alocação de roteadores, projeto de rede de distribuição e várias outras, e são bastante estudados tanto do ponto de vista prático como teórico. No entanto, por diversas vezes, restrições mais realistas devem ser feitas sobre os modelos, como impor uma limitação na capacidades dos roteadores. Enquanto os problemas tradicionais sem restrições são bem compreendidos, com vários algoritmos de aproximação, as versões com restrições têm desafiado os pesquisadores e a literatura de algoritmos sobre elas é mais escassa. Por exemplo, embora se conheça uma 2-aproximação para o problema dos k-centros desde a década de 1980, que é a melhor possível sob a hipótese de PP ` NP, o primeiro algoritmo com aproximação constante para o k-centros com capacidades só foi descoberto em 2012; para o problema das k-medianas com capacidades ainda não há qualquer aproximação constante. Recentemente, novas técnicas, especialmente as baseadas em programação linear, têm se mostrado promissoras para problemas sujeitos a restrições. O candidato tem profundo conhecimento sobre problemas de projeto de rede e técnicas de programação linear, tendo obtido vários resultados relacionados a esses temas em seu doutorado. Desse modo, este projeto é uma oportunidade de combinar a formação do candidato e a experiência em algoritmos de aproximação da supervisora para obter resultados que atualmente estão na fronteira do conhecimento. (AU) | |
| 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) | |