Approximation Issues of Combinatorial Optimization Problems Induced by Optimal Piecewise-Linear Learning Procedures

摘要

The known empirical risk minimization (ERM) method, which is used to construct learning procedures, is closely related to a number of combinatorial optimization problems that are hard to solve in the majority of cases. The properties of one of such problem, namely the Minimum Affine Separating Committee problem, which arises at learning stage in the category of piecewise-linear recognition algorithms, are inves tigated in this paper. New results in the field of computational complexity and approximability of the problem and its subcategories are discussed.