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


Sergei Chubanov
An improved polynomial relaxation-type algorithm for linear programming


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(n3Lmin) time where n is the number of variables
and Lmin 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(n4) time. This theoretical estimate is less by the factor of n2 than that of our previous algorithm.


Talk 1 of the contributed session Mon.3.MA 042
"Linear optimization" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  The system of instant Payday Loans Virginia allows any adult U.S. citizen. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.