TR00-017 Authors: Valentin E. Brimkov, Stefan S. Dantchev

Publication: 6th March 2000 16:27

Downloads: 1887

Keywords:

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 \).