Bases de Hilbert / Hilbert Basis
AUTOR(ES)
Marcelo Hashimoto
DATA DE PUBLICAÇÃO
2007
RESUMO
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éodorys 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éodorys theorem and related conjectures.
ASSUNTO(S)
total dual integrality combinatorial optimization duality theorem relações min-max programação inteira teorema de carathéodory otimização combinatória programação linear min-max relations carathéodory s theorem linear programming total dual integralidade bases de hilbert teorema da dualidade hilbert basis integer programming
