scientific article; zbMATH DE number 3880440

From MaRDI portal
Publication:3346090





[For the entire collection see Zbl 0535.00030.] In the paper of \textit{J. J. Bartholdi, J. B. Orlin} and \textit{H. D. Ratliff} [Oper. Res. 28, 1074-1085 (1980; Zbl 0451.90075)] a special case of a linear integer problem is solved by a very simple algorithm. The idea is first to solve the corresponding linear program and from the resulting solution \(x^ 0\) to obtain the integer solution \(x^*\) by a simple transformation, say \(x^*=T^{-1}\lceil Tx^ 0\rceil\). They also adress the question to describe the class of integer problems solvable in such a way. The answer is given by the author in Theorem 4, which gives the following necessary and sufficient conditions for the application of the above-mentioned procedure: (1) T and \(T^{-1}\) are integer; (2) \(T^{-1}\) has at most one negative entry in each row, equal to -1; (3) \(AT^{-1}\) has at most one negative entry in each row, equal to -1.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3346090)