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. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-08102007-121713 |
| Date | 28 February 2007 |
| Creators | Marcelo Hashimoto |
| Contributors | Jose Coelho de Pina Junior, Paulo Feofiloff, Orlando Lee |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0301 seconds