Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-017 | 3rd March 2000 00:00

On the Algebraic Complexity of Integer Programming

RSS-Feed




TR00-017
Authors: Valentin E. Brimkov, Stefan S. Dantchev
Publication: 6th March 2000 16:27
Downloads: 3655
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