Algoritmos para Problemas de Otimização Combinatória: Projeto, Análise e Experimentação

Problemas de otimização combinatória surgem de aplicações práticas importantes em diversas áreas da ciência e da indústria, como por exemplo em Biologia Molecular, nas Engenharias, em Geoprocessamento, em Finanças, etc. Soluções determinísticas exatas e eficientes para uma parcela desses problemas são encontradas na literatura e ainda surgem em aplicações práticas dessas áreas. No entanto, para uma parcela significativa desses problemas, tais soluções não podem ser encontradas de forma computacionalmente eficiente. Algoritmos de aproximação, determinísticos e probabilísticos, são então projetados e garantem eficiência e qualidade da solução apresentada. Experimentos computacionais são também realizados para verificação dessas propriedades. Neste projeto pretendemos investigar alguns problemas de otimização combinatória com os quais os participantes têm tido contato mais recentemente: o problema de Steiner em grafos e suas restrições, problemas envolvendo redes metabólicas e problemas envolvendo características evolutivas dos cromossomos sexuais de humanos. Os resultados obtidos até o momento motivam-nos a continuar o desenvolvimento de pesquisas sobre esses problemas, na tentativa de continuar propondo algoritmos de aproximação para os problemas mencionados e para outros variantes seus.

Coordenador: Fábio Henrique Viduani Martinez