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.

Presented by the member of Editorial Board: A. I. Kibzun