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

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)