Approximation issues of combinatorial optimization problems induced by optimal piecewise-linear learning procedures / Khachai M.Y. // Pattern Recognition and Image Analysis. - 2011. - V. 21, l. 2. - P. 144-147.

ISSN:

10546618

Type:

Article

Abstract:

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 investigated in this paper. New results in the field of computational complexity and approximability of the problem and its subcategories are discussed. © 2011 Pleiades Publishing, Ltd.

Author keywords:

Index keywords:

Approximability; Combinatorial optimization problems; Empirical risk minimization; Learning procedures; New results; Piecewise-linear; Recognition algorithm; Computational complexity; Optimization; Pi

DOI:

10.1134/S1054661811020489

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-79959267326&doi=10.1134%2fS1054661811020489&partnerID=40&md5=b92f9ef9fcc35930628398754b90ce62

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-79959267326&doi=10.1134%2fS1054661811020489&partnerID=40&md5=b92f9ef9fcc35930628398754b90ce62
Affiliations	Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620990, Russian Federation
References	Lin, J., Vitter, J., Complexity Results on Learning by Neural Nets (1991) Mach. Learn, 6, pp. 211-230; Khachay, M., On the Computational Complexity of the Minimum Committee Problem J. Math. Model. Algor, 6 (4), pp. 547-561; Khachai, M., Poberii, M., Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position (2009) Informat., 20 (2), pp. 217-234; Dinur, I., The PCP Theorem by Gap Amplification (2007) J. ACM, 54 (3); Mazurov, V.D., Kibernet (1971) Committees of Inequalities Systems and a Pattern Recognition Problem, 3, pp. 140-146; Khachai, M., Computational and Approximational Complexity of Combinatorial Problems Related to the Committee Polyhedral Separability of Finite Sets (2008) Pattern Recogn. Image Anal., 18 (2), pp. 237-242; Megiddo, N., Tamir, A., On the Complexity of Locating Linear Facilities in the Plane (1982) Operat. Res. Lett., 1 (5), pp. 194-197
Correspondence Address	Khachai, M. Y.; Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg 620990, Russian Federation; email: mkhachay@imm.uran.ru
Language of Original Document	English
Abbreviated Source Title	Pattern Recogn. Image Anal.
Source	Scopus