skip to main content
Idioma:

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

De Carli Silva, Marcel Kenji

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 2007-04-04

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Relações min-max em otimização combinatória
  • Autor: De Carli Silva, Marcel Kenji
  • Orientador: Wakabayashi, Yoshiko
  • Assuntos: Otimização Combinatória; Relações Min-Max; Teoria Dos Grafos; Combinatorial Optimization; Graph Theory; Min-Max Relations
  • Notas: Dissertação (Mestrado)
  • Descrição: 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ão. 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 suficiente 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ções 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. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, 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.
  • DOI: 10.11606/D.45.2007.tde-08052007-182205
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 2007-04-04
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.