Relações min-max em otimização combinatória (2007)
- Autores:
- Autor USP: SILVA, MARCEL KENJI DE CARLI - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: OTIMIZAÇÃO COMBINATÓRIA
- Agências de fomento:
- Idioma: Português
- Resumo: 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
-
ABNT
SILVA, Marcel Kenji de Carli. Relações min-max em otimização combinatória. 2007. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2007. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/. Acesso em: 19 abr. 2024. -
APA
Silva, M. K. de C. (2007). Relações min-max em otimização combinatória (Dissertação (Mestrado). 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. Relações min-max em otimização combinatória [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/ -
Vancouver
Silva MK de C. Relações min-max em otimização combinatória [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08052007-182205/ - An axiomatic duality framework for the theta body and related convex corners
- Sparse sums of positive semidefinite matrices
- A notion of total dual integrality for convex, semidefinite, and extended formulations
- An axiomatic duality framework for the theta body and related convex corners
- Vertices of spectrahedra arising from the elliptope, the theta body, and their relatives
- Commute time as a method to explore brain functional connectomes
- Strict complementarity in semidefinite optimization with elliptopes including the maxCut SDP
- Algebras, graphs and thetas
- A randomized approximation algorithm for the weighted fractional cut-covering problem
- Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
