Minimização de funções submodulares

Autor(es)

Juliana Barby Simão

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2009-06-09

Membros da banca

Jose Coelho de Pina Junior; Orlando Lee; Arnaldo Mandel

• Orientador: Jose Coelho de Pina Junior

Resumo

Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Pode-se dizer que o papel desempenhado por essas funções em otimização discreta é similar ao desempenhado por convexidade em otimização contínua. Com efeito, muitos problemas em otimização combinatória podem ser formulados como um problema de minimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algorítmicos de funções submodulares, com ênfase nos recentes avanços em algoritmos combinatórios para minimização dessas funções. Descrevemos com detalhes os primeiros algoritmos combinatórios e fortemente polinomiais para esse propósito, devidos a Schrijver e Iwata, Fleischer e Fujishige, além de algumas outras extensões. Aplicações de submodularidade em otimização combinatória também estão presentes neste trabalho. (AU)

• Processo FAPESP: 04/11340-8 - Aspectos de submodularidade em otimizacao combinatoria.
• Beneficiário: Juliana Barby Simao
• Modalidade de apoio: Bolsas no Brasil - Mestrado