Approximating integer programs with positive right-hand sides
We study minimisation of integer linear programs with positive right-hand sides. We show that such programs can be approximated within the maximum absolute row sum of the constraint matrix A whenever the variables are allowed to take values in N. This result is optimal under the unique games conjecture. When the variables are restricted to bounded domains, we show that finding a feasible solution is NP-hard in almost all cases. (C) 2010 Elsevier B.V. All rights reserved.
integer programming approximation algorithms