Improved algorithms for integer programming and related lattice problems

ABSTRACT

The integer programming problem is: Given m×n and m×l matrices A and b respectively of integers, find whether, there exists an all integer n×l vector x satisfying the m inequalities A×≤b. In settling an important open problem, Lenstra (1981) showed in an elegant way that when n, the number of dimensions is fixed, there is a polynomial-time algorithm to solve this problem. His algorithm achieves a running-time of 0(cn3•p(length of data)) where p is some polynomial and c a constant independent of n. Since such an algorithm has several important applications - cryptography (Shamir (1982)), diophantine approximations (Lagarias (1982)), coding theory (Conway and Sloane (1982), etc. it is important to improve the running time. We present an algorithm here that has a running time of 0(n9nL log L) where L is the length of the input. Whereas Lenstra's algorithm in the worst case reduces an n-dimensional problem to cn2−(n−) dimensional problems, our algorithm effectively reduces an n-dimensional problem to at most polynomially many (n−1) dimensional problems, thus achieving our time bound. The algorithm we propose, first finds a “more orthogonal” basis for a lattice (see the next section for the definition of a lattice) than those of Lenstra (1981) and Lenstra, Lenstra and Lovasz (1982), but in time 0(ndn poly (length of input)). It then uses an enumeration technique to solve integer programming and related problems. While this paper presents mainly the theoretical improvements that can be made in the algorithms, we discuss in section 6 why in practice our estimates of running time may be overly pessimistic. The last part of the paper discusses some complexity issues. It is an interesting open problem as to whether finding the Euclidean shortest non-zero vector of a given lattice is NP-hard. (See Lenstra (1981), Van Emde Boas (1981) and Lagarias (1982)).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Van Emde Boas, "Another NP-complete problem and the complexity of computing short vectors in a lattice", IEEE Transactions on Information Theory, Vol. IT-28, No. 2 (1982).
• 3: J.W.S. Cassels, "An Introduction to the geometry of numbers", Springer, Heidelberg (1959).
• 4: Conway and Sloane, "Fast quantizing and decoding algorithms for lattice quantizers and codes", IEEE Transactions on Information Theory, Vol. IT-28, No. 2, (1982).
• 5: R. Kannan and A. Bachem, "Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix", SIAM J. on Comp. 8(1979).
• 6: J.C. Lagarias, "Computational complexity of simultaneous diophantine approximation problems", 23rd FOCS (1982).
• 7: A.K. Lenstra, H.W. Lenstra Jr. and L. Lovasz, "Factoring polynomials with rational coefficients", Report 82-05, Mathematisch Instituut, Universiteit Amsterdam (1982).
• 8: H.W. Lenstra, Jr., "Integer programming with a fixed number of variables", Report 81-03, Mathematisch Instituut, Universiteit ban Amsterdam (1981).
• 9: A. Shamir, "A polynomial-time algorithm for breaking the basic Merkle-Hellman crypto system", 23rd FOCS (1982).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Theory