Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR00-017 | 3rd March 2000 00:00

#### On the Algebraic Complexity of Integer Programming

TR00-017
Authors: Valentin E. Brimkov, Stefan S. Dantchev
Publication: 6th March 2000 16:27
Keywords:

Abstract:

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