Busca avançada
Ano de início
Entree

Algoritmos de aproximação para problemas de projeto de rede com restrições

Processo: 14/14209-1
Linha de fomento:Bolsas no Brasil - Pós-Doutorado
Vigência (Início): 01 de novembro de 2014
Vigência (Término): 31 de julho de 2015
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Convênio/Acordo: 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

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)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
FERNANDES, CRISTINA G.; DE PAULA, SAMUEL P.; PEDROSA, LEHILTON L. C. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. ALGORITHMICA, v. 80, n. 3, SI, p. 1041-1072, MAR 2018. Citações Web of Science: 2.
MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.; SCHOUERY, RAFAEL C. S.; DE SOUZA, RENATA G. D. A PTAS for the Geometric Connected Facility Location Problem. THEORY OF COMPUTING SYSTEMS, v. 61, n. 3, p. 871-892, OCT 2017. Citações Web of Science: 0.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.
Mapa da distribuição dos acessos desta página
Para ver o sumário de acessos desta página, clique aqui.