• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  Bookmark and Share
Master's Dissertation
Full name
Marcelo Hashimoto
Knowledge Area
Date of Defense
São Paulo, 2007
Pina Junior, Jose Coelho de (President)
Feofiloff, Paulo
Lee, Orlando
Title in Portuguese
Bases de Hilbert
Keywords in Portuguese
bases de Hilbert
otimização combinatória
programação inteira
programação linear
relações min-max
teorema da dualidade
teorema de Carathéodory
total dual integralidade
Abstract in Portuguese
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.
Title in English
Hilbert Basis
Keywords in English
Carathéodory's theorem
combinatorial optimization
duality theorem
Hilbert basis
integer programming
linear programming
min-max relations
total dual integrality
Abstract in English
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.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
dissertacao.pdf (1.90 Mbytes)
Publishing Date
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2024. All rights reserved.