A rounding algorithm for integer programs (Q1327212): Difference between revisions

The integer program (IP): \(\min cx\) subject to \(Ax\geq b\), \(x\) integer, is under consideration. Firstly, a linear program is solved, then a rounding procedure is proposed, that is an algorithm to transform a received solution to an integer vector. This algorithm is polynomial. The authors obtain a sufficient condition on \(A\), \(b\), \(c\) such that the rounding procedure gives a solution of the initial IP: all components of \(c\) are 1, \(b\) is any integer vector, \(A\) consists of 0 or 1 and has the one-drop property, that is there exists a permutation of columns of \(A\) so that in each row the elements are in nondecreasing order except possibly in one position, but in this case decreasing is only 1. The authors propose a polynomial algorithm to test a one-drop property for some classes of matrices \(A\). An attempt to find a polynomial algorithm to check a one- drop property in the general case was unsuccessful.