Computational Complexity of Combinatorial Problems Relatedto Piecewise Linear Committee Pattern-RecognitionLearning Procedures

摘要

A class of combinatorial optimization problems related to optimal pattern recognition learning is studied by the method of structural risk minimization in the class of piecewise linear committee decision rules. Most of the problems are shown to be intractable and the thresholds of their efficient approximability are estimated and approximation polynomial algorithms are given.