**Monday, 15:15 - 15:40 h, Room: MA 042**

**Sergei Chubanov**

An improved polynomial relaxation-type algorithm for linear programming

**Abstract:**

To find a solution of a system of linear inequalities, the

classical relaxation method projects the current point, at every iteration, onto a hyperplane defined by a violated constraint. The constructed sequence converges to a feasible solution. It is well known that the method is not polynomial. One of the reasons for this is that each iteration considers only one violated constraint among the original constrains of the system. Unlike the relaxation method, each iteration of our algorithm considers an appropriate nonnegative linear combination of the inequalities. The algorithm runs in *O(n*^{3}L_{min}) time where *n* is the number of variables

and *L*_{min} is the minimum binary size of a feasible solution. In particular, the algorithm either finds a nonnegative solution of a system of linear equations or proves that there are no *0,1*-solutions in *O(n*^{4}) time. This theoretical estimate is less by the factor of *n*^{2} than that of our previous algorithm.

Talk 1 of the contributed session Mon.3.MA 042

**"Linear optimization"** [...]

Cluster 11

**"Integer & mixed-integer programming"** [...]