Ver registro no DEDALUS
Exportar registro bibliográfico

Minimização de funções submodulares (2009)

  • Authors:
  • USP affiliated authors: SIMÃO, JULIANA BARBY - IME
  • USP Schools: IME
  • Subjects: OTIMIZAÇÃO COMBINATÓRIA
  • 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
  • Acesso online ao documento

    Online access or search this record in

    Exemplares físicos disponíveis nas Bibliotecas da USP
    BibliotecaCód. de barrasNúm. de chamada
    IME31000062594IME-T QA845.T S588m e.1
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SIMÃO, Juliana Barby; PINA JÚNIOR, José Coelho de. Minimização de funções submodulares. 2009.Universidade de São Paulo, São Paulo, 2009. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/?&lang=pt-br >.
    • APA

      Simão, J. B., & Pina Júnior, J. C. de. (2009). Minimização de funções submodulares. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/?&lang=pt-br
    • NLM

      Simão JB, Pina Júnior JC de. Minimização de funções submodulares [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/?&lang=pt-br
    • Vancouver

      Simão JB, Pina Júnior JC de. Minimização de funções submodulares [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-03112010-231536/?&lang=pt-br

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: