期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILPR) : Given a matrix ARmn and vectors
bRm, dRn, decide if there is xZn such that
Axb, where 0xd.
We show that there is an Omlogd algorithm for ILPR, when the value of n is fixed.
As a consequence, we obtain a tight algebraic complexity bound log1amin , amin=mina1an for the Knapsack problem
(KPR) : Given aRn+, decide if there is xZn such that aTx=1, when the dimension n is fixed.
We achieve these results in particular through a careful analysis of the algebraic complexity of the Lov\'asz' basis reduction algorithm and Kannan-Bachem's Hermite normal form algorithm, which may be of interest in its own.
We also obtain an Omn5lognn+logd depth {\em algebraic
decision tree} for ILPR, for every m and n.
关键词：algebraic complexity, integer programming, Knapsack Problem
