On the complexity of integer programming in the blum-shub-smale computational model

Abstract

In the framework of the Blum-Shub-Smale real number model [3], we study the algebraic complexity of the integer linear programming problem (ILPR) : Given a matrix A 2 Rmn and vectors b 2 Rm, d 2 Rn, decide whether there is x 2 Zn such that Ax ? b, where 0 ? x ? d. The main contributions of the paper are the following: An O (mlog jjdjj) algorithm for ILPR, when the value of n is fixed. As a corollary, we obtain under the same restriction a tight algebraic complexity bound log 1 min , amin = minfa1; : : : ; ang, for the knapsack problem (KPR) : Given a 2 Rn +, decide whether there is x 2 Zn such that aT x = 1. We achieve these results in particular through a careful analysis of the algebraic complexity of the Lovasz' basis reduction algorithm and the Kannan-Bachem's Hermite normal form algorithm, which may be of interest in its own. An O mn5 log n (n + log jjdjj) depth algebraic decision tree for ILPR, for every m and n. A new lower bound for 0/1 KPR. More precisely, no algorithm can solve 0/1 KPR in o (n log n) f(a1; : : : ; an) time, even if f is an arbitrary continuous function of n variables. This result appears as an alternative to the well-known Ben-Or's bound (n2) [1] and is independent upon it. © Springer-Verlag Berlin Heidelberg 2002.