Bases de Hilbert

• Ano de defesa: 2007
• Autor(a) principal: Hashimoto, Marcelo
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: bases de Hilbert; Carathéodory's theorem; combinatorial optimization; duality theorem; Hilbert basis; integer programming; linear programming; min-max relations; otimização combinatória; programação inteira; programação linear; relações min-max; teorema da dualidade; teorema de Carathéodory; total dual integralidade; total dual integrality
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-08102007-121713/

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas.