a École Polytechnique, LIX (CNRS UMR 7161), Palaiseau, France b Department of Computer and Information Science, Linköping University, Linköping, Sweden c Max Planck Institute for Human Development, Berlin, Germany
Abstract:
We present an efficient algorithm to find an optimal integer solution of a given system of 2-variable equalities and 1-variable inequalities with respect to a given linear objective function. Our algorithm has worst-case running time in O(N2) where N is the number of bits in the input.