Minimização de funções submodulares (2009)
- Authors:
- Autor USP: SIMÃO, JULIANA BARBY - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: 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 deminimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e frequentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algoritmicos 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.
- Imprenta:
- Data da defesa: 09.06.2009
-
ABNT
SIMÃO, Juliana Barby. Minimização de funções submodulares. 2009. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/. Acesso em: 12 jun. 2024. -
APA
Simão, J. B. (2009). Minimização de funções submodulares (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/ -
NLM
Simão JB. Minimização de funções submodulares [Internet]. 2009 ;[citado 2024 jun. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/ -
Vancouver
Simão JB. Minimização de funções submodulares [Internet]. 2009 ;[citado 2024 jun. 12 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
