Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-017 | 3rd March 2000 00:00

On the Algebraic Complexity of Integer Programming


Authors: Valentin E. Brimkov, Stefan S. Dantchev
Publication: 6th March 2000 16:27
Downloads: 1338


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
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x \in {\bf Z}^n$ such that
$Ax \leq b$, where ${\bf 0} \leq x \leq d$.

We show that there is an \( O\left( m\log ||d||\right) \) algorithm for ILP\( _{\bf R} \), when the value of \( n \) is fixed.
As a consequence, we obtain a tight algebraic complexity bound $\Theta \left( \log \frac{1}{a_{\min}}\right)$, $a_{\min} = \min \{ a_1,\dots,a_n \}$ for the Knapsack problem
(KP$_{\bf R}$) : Given $a \in {\bf R}_{+}^n$, decide if there is $x \in {\bf Z}^n$ such that $a^T x = 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 \( O\left( mn^{5}\log n\left( n+\log ||d||\right) \right) \) depth {\em algebraic
decision tree} for ILP\( _{\bf R} \), for every \( m \) and \( n \).

ISSN 1433-8092 | Imprint