| Processo: | 04/11340-8 |
| Linha de fomento: | Bolsas no Brasil - Mestrado |
| Vigência (Início): | 01 de março de 2005 |
| Vigência (Término): | 28 de fevereiro de 2007 |
| Área do conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação |
| Pesquisador responsável: | José Coelho de Pina Junior |
| Beneficiário: | Juliana Barby Simao |
| Instituição-sede: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil |
| Assunto(s): | Programação linear inteira Combinatória poliédrica Matroides |
Resumo Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Em vários teoremas e problemas combinatórios, submodularidade está envolvida de uma forma ou outra e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Este projeto de dissertação de mestrado pretende estudar aspectos estruturais e algorítmicos de funções submodulares e de suas aplicações em otimização combinatória. Mencionamos que em 2003 foi publicado um número especial do jornal Discrete Applied Mathematics inteiramente dedicado a submodularidade, o que evidencia a relevância da área. (AU) | |