Let A be a fixed integer matrix of size m by n and consider all b for which the body is full dimensional. We examine the set of shortest non-zero integral vectors with respect to the family of norms. We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree at the polynomial bound.
Let p = (p1,…,pn) be a vector of positive integers whose greatest common divisor is unity. The Frobenius problem is to find the largest integer f* which cannot be written as a non-negative integral combination of the pi. In this note we relate the Frobenius problem to the topic of maximal lattice free bodies and describe an algorithm for n = 3.
Let F(x) be a convex function defined in Rn, which is symmetric about the origin and homogeneous of degree 1, and let L be the lattice of integers Zn. A definition of a reduced basis, b1, …, bn, of the lattice with respect to the distance function F is presented, and we describe an algorithm which yields a reduced basis in polynomial time, for fixed n. In the special case in which the bodies {x: F(x) < t} are ellipsoids, the definition of a reduced basis is identical with that given by Lenstra, Lenstra and Lovasz (1982) and the algorithm is the well known basis reduction algorithm.
We show that the basis vector b1, in a reduced basis, is an approximation to a shortest non-zero lattice point with respect to F and relate the basis vectors bi to Minkowski’s successive minima. The results lead to an algorithm for integer programming which executes in polynomial time for fixed n, but which avoids the ellipsoidal approximation required by Lenstra’s algorithm. We also discuss the properties of a Korkine-Zolotarev basis for the lattice.
Let p = (p1,…,pn) be a vector of positive integers whose greatest common divisor is unity. The Frobenius problem is to find the largest integer f* which cannot be written as a non-negative integral combination of the pi. In this note we relate the Frobenius problem to the topic of maximal lattice free bodies and describe an algorithm for n = 3.
Let F(x) be a convex function defined in Rn, which is symmetric about the origin and homogeneous of degree 1, and let L be the lattice of integers Zn. A definition of a reduced basis, b1, …, bn, of the lattice with respect to the distance function F is presented, and we describe an algorithm which yields a reduced basis in polynomial time, for fixed n. In the special case in which the bodies {x : F(x) < t} are ellipsoids, the definition of a reduced basis is identical with that given by Lenstra, Lenstra and Lovasz (1982) and the algorithm is the well known basis reduction algorithm.
We show that the basis vector b1, in a reduced basis, is an approximation to a shortest non-zero lattice point with respect to F and relate the basis vectors bi to Minkowski’s successive minima. The results lead to an algorithm for integer programming which executes in polynomial time for fixed n, but which avoids the ellipsoidal approximation required by Lenstra’s algorithm. We also discuss the properties of a Korkine-Zolotarev basis for the lattice.
Keywords: Reduced basis, lattice point, integer programming
The paper discusses the analogy between economic institutions and algorithms for the solution of mathematical programming problems. The simplex method for solving linear programs can be interpreted as a search for market prices that equilibrate the demand for factors of production with their supply. An interpretation in terms of the internal organization of the large firm is offered for Lenstra’s integer programming algorithm.
The paper discusses the analogy between economic institutions and algorithms for the solution of mathematical programming problems. The simplex method for solving linear programs can be interpreted as a search for market prices that equilibrate the demand for factors of production with their supply. An interpretation in terms of the internal organization of the large firm is offered for Lenstra’s integer programming algorithm.
Keywords: Integer programming, prices, factors of production, algorithms
(Edited with John B. Shoven) This book presents a collection of articles on applied general equilibrium analysis by major contributors to this field. This rapidly expanding method of analysis involves the use of computers to study entire economies and the interrelationships among firms, households and governments in these economies. There are also articles on the particular computational techniques involved in the numerical estimation of these equilibrium models and on several particular applications. Papers deal with the United States, Mexican and Australian economies. Other chapters provide an analysis of long-run energy problems, fiscal federalism and economic planning.