ECCC-Report TR00-017https://eccc.weizmann.ac.il/report/2000/017Comments and Revisions published for TR00-017en-usMon, 06 Mar 2000 16:27:11 +0200
Paper TR00-017
| On the Algebraic Complexity of Integer Programming |
Valentin E. Brimkov,
Stefan S. Dantchev
https://eccc.weizmann.ac.il/report/2000/017In 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 \).
Mon, 06 Mar 2000 16:27:11 +0200https://eccc.weizmann.ac.il/report/2000/017