Exportar registro bibliográfico

Relações min-max em otimização combinatória (2007)

  • Authors:
  • Autor USP: SILVA, MARCEL KENJI DE CARLI - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assunto: OTIMIZAÇÃO COMBINATÓRIA
  • Agências de fomento:
  • Language: Português
  • Abstract: Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em queståqao. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficient5e sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificação disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Paratanto, usamos um teorema de Frank, Tardos e Sebõ e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas
  • Imprenta:
  • Data da defesa: 04.04.2007
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SILVA, Marcel Kenji de Carli; WAKABAYASHI, Yoshiko. Relações min-max em otimização combinatória. 2007.Universidade de São Paulo, São Paulo, 2007. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/ >.
    • APA

      Silva, M. K. de C., & Wakabayashi, Y. (2007). Relações min-max em otimização combinatória. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/
    • NLM

      Silva MK de C, Wakabayashi Y. Relações min-max em otimização combinatória [Internet]. 2007 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/
    • Vancouver

      Silva MK de C, Wakabayashi Y. Relações min-max em otimização combinatória [Internet]. 2007 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/


Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020