scientific article; zbMATH DE number 3880440
[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.
- A rounding algorithm for integer programs
- Total dual integrality of the linear complementarity problem
- On exact selection of minimally unsatisfiable subformulae
- An extension of a theorem of Fulkerson and Gross
- Parametric formulation of the general integer linear programming problem
- Simple majority rule and integer programming
- Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
- A combinatorial algorithm for Horn programs
- The Linear Complementarity Problems with a Few Variables per Constraint
- Trichotomy for integer linear systems based on their sign patterns
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)