A ROUNDING ALGORITHM FOR INTEGER PROGRAMS

There exist general purpose algorithms to solve the integer linear pro gramming problem but none of them are polynomial. Polynomially bounded rounding algorithms have been studied, but most of them are problem s pecific. In this paper we study a generalized rounding algorithm that is polynomial, characterize matrices that may be used in this scheme a nd identify a class of integer programs that it solves.