| Processo: | 12/17634-0 |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |
| Data de Início da vigência: | 01 de fevereiro de 2013 |
| Data de Término da vigência: | 31 de janeiro de 2014 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Flávio Keidi Miyazawa |
| Beneficiário: | Lehilton Lelis Chaves Pedrosa |
| Supervisor: | Maxim Sviridenko |
| Instituição Sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Instituição Anfitriã: | University of Warwick, Inglaterra |
| Vinculado à bolsa: | 10/20710-4 - Algoritmos de Aproximação para Problemas de Localização com Diferentes Funções de Distância, BP.DR |
| Assunto(s): | Algoritmos de aproximação Alocação de recursos |
| Palavra(s)-Chave do Pesquisador: | Algoritmos de Aproximação | Arredondamento de PL | cadeia de fornecimento | Método Primal-dual | Problema de Alocação de Recursos | Programa Revelador de Fator | Algoritmos de Aproximação |
Resumo Algoritmos de aproximação têm recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Esses algoritmos são utilizados principalmente em problemas NP-difíceis, para os quais um algoritmo exato seria inviável. Existem diferentes técnicas para o desenvolvimento de algoritmos de aproximação, que têm sido utilizadas para obter aproximações cada vez melhores para os problemas de alocação e vários outros. Essas técnicas geralmente podem ser utilizadas para lidar com diversas variantes e outros problemas de cadeia de suprimento. Neste projeto, estamos interessados em investigar o Problema de Alocação de Recursos (FLP) e outros problemas de cadeia de suprimento, como o Problema de Gerência de Estoque. Nosso interesse será focado em estratégias recentes desenvolvidas para estes problemas, principalmente aquelas que levam a bons fatores de aproximação. Entre elas, estão as técnicas de arredondamento de PL e a técnica primal-dual. Em particular, a técnica primal-dual combinada com a análise por meio de programas reveladores de fator (factor-revealing programs). Um primeiro objetivo desse projeto é estudar essas técnicas e aplicá-las a variantes e problemas relacionados. Também iremos investigar diferentes funções de distância para os problemas estudados. Diversos algoritmos de aproximação para problemas, como o FLP ou o TSP, utilizam fortemente o fato de que as funções de distância subjacentes sejam métricas para obter resultados de aproximação. Para algumas aplicações, no entanto, as funções de distância não obedecem à desigualdade triangular, como é o caso do k-means, que utiliza a distância euclidiana ao quadrado. Os problemas TSP e FLP já foram estudados considerando funções de distância não-métricas. Um outro objetivo desse trabalho é estender esse estudo a outras variantes e problemas relacionados. (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) | |