METHOD OF ALTERNATING CONTRACTIONS AND ITS APPLICATIONS TO SOME CONVEX OPTIMIZATION PROBLEMS

This article proposes an algorithm for convex programming which can be viewed as a further development of the method of alternating projections. Some combinatorial problems like the maximum matchings and the maximum simple b-matchings can be solved in polynomial time by this algorithm. More generally, it runs in polynomial time for any binary linear problem where the objective function is defined by a binary vector and the convex hull of the feasible set can be described by a system of the form Ax <= b, x >= 0, given by a polynomial-time separation oracle, where A is a nonnegative matrix. Also, our algorithm is an Fully polynomial time approximation Scheme for a wide range of optimization problems with an exponential or infinite number of constraints given by a separation oracle.

Automated summary

The proposed algorithm in this article is an advancement of alternating projections method for convex programming. It can efficiently solve combinatorial optimization problems in polynomial time. Additionally, it is a Fully polynomial time approximation Scheme for a wide range of optimization problems with an exponential or infinite number of constraints.