a Department of Statistics and Operations Reseach, 40 West 4th Street, Room 524, New York University, New York, NY 10003, USA
b School of Management, The University of Texas at Dallas, P.O. Box 830688, Richardson, TX 75083-0688, USA
Abstract:
There exist general purpose algorithms to solve the integer linear programming problem but none of them are polynomial. Polynomially bounded rounding algorithms have been studied, but most of them are problem specific. In this paper we study a generalized rounding algorithm that is polynomial, characterize matrices that may be used in this scheme and identify a class of integer programs that it solves.