Scheme of boosting in the problems of combinatorial optimization induced by the collective training algorithms

The game approach generalizing the traditional boosting scheme was applied to the construction of a polynomial algorithm for the well‐known intractable problem of the minimal affine committee separating the finite subsets of the real linear space of a fixed dimensionality under an additional condition of generality of positions of the separated sets (MASC‐GP(n) problem). It was shown that the proposed algorithm currently features a record guaranteed estimate of precision.