Scheme of boosting in the problems of combinatorial optimization induced by the collective training algorithms / Khachai M.Y., Poberii M.I. // Automation and Remote Control. - 2014. - V. 75, l. 4. - P. 657-667.

ISSN:
00051179
Type:
Article
Abstract:
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. © 2014 Pleiades Publishing, Ltd.
Author keywords:
Index keywords:
Automation; Control; Collective trainings; Finite subsets; Game approach; Linear spaces; Polynomial algorithm; Separated sets; Algorithms
DOI:
10.1134/S0005117914040067
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-84899583210&doi=10.1134%2fS0005117914040067&partnerID=40&md5=67202a07574607e8a77ce6827eb26702
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-84899583210&doi=10.1134%2fS0005117914040067&partnerID=40&md5=67202a07574607e8a77ce6827eb26702
Affiliations Krasovskii Institute of Mathematics and Mechanics, Ural Branch, Sian Academy of Sciences, Yekaterinburg, Russian Federation; Ural Federal University, Yekaterinburg, Russian Federation
References Eremin, I.I., Mazurov, V., Astaf'Ev, N.N., (1983) Nesobstvennye Zadachi Lineinogo i Vypuklogo Programmirovaniya, , Nauka Moscow (Improper Problems Linear and Convex Programming); Eremin, I.I., (1988) Protivorechivye Modeli optimal'Nogo Planirovaniya, , Nauka Moscow 0657.90058 (Contradictory Models of Optimal Planning); Mazurov, V., (1990) Metod Komitetov v Zadachakh Optimizatsii i Klassifikatsii, , Nauka Moscow 0743.90100 (Method of Committees in the Problems of Optimization and Classification); Mazurov, V., Khachai, M., Committee Constructions (1999) Izv. Ural. Gos. Univ., 14, pp. 76-108; Khachai, M., Mazurov, V., Rybin, A., Committee Construction for Solving Problems of Selection, Diagnostics, and Prediction (2002) Proc. Steklov Inst. Math., pp. 67-S101; Khachai, M., Computational Complexity of the Minimum Committee Problem and Related Problems (2006) Dokl. Math., 73 (1), pp. 138-141. , 10.1134/S1064562406010376 1155.94396 3050486; Mazurov, V., Khachai, M., Committees of Systems of Linear Inequalities (2004) Autom. Remote Control, 65 (2), pp. 193-203. , 10.1023/B:AURC.0000014716.77510.61 1066.90053 2093418; Mazurov, V., Khachai, M., Parallel Computations and Committee Constructions (2007) Autom. Remote Control, 68 (5), pp. 912-921. , 10.1134/S0005117907050165 1169.68576 2333040; Kobylkin, K.S., Constraint Elimination Method for the Committee Problem (2012) Autom. Remote Control, 73 (2), pp. 355-368. , 10.1134/S0005117912020130; Mazurov, V., System Inequality Committees and the Pattern Recognition Problem (1971) Kibernetika, pp. 140-146; Schapire, R., Freund, Y., (2012) Boosting: Foundations and Algorithms, , MIT Press Cambridge; Elster, K.-H., Reinhardt, R., Schäuble, M., Donath, G., (1977) Einführung in Die Nichtlineare Optimierung, , Teubner Leipzig 0389.90063 Translated under the title Vvedenie v nelineinoe programmirovanie, Eremin, I.I. Ed. Moscow: Nauka, 1985; Khachai, M., Computational and Approximational Complexity of Combinatorial Problems Related to the Committee Polyhedral Separability of Finite Sets (2008) Patt. Recogn. Image Anal., 18 (2), pp. 237-242; Khachai, M., Poberii, M., Complexity and Approximability of Committee Polyhedral Separability of Sets in General Position (2009) Informatika, 20 (2), pp. 217-234. , 2554372; Freund, Y., Boosting a Weak Algorithm by Majority (1995) Inform. Comput., 121, pp. 256-285. , 10.1006/inco.1995.1136 0833.68109 1348530; Gainanov, D.N., Novokshenov, V.A., Tyagunov, L.I., On Graphs Generated by the Incompatible Systems of Linear Inequalities (1983) Mat. Zametki, 33 (2), pp. 293-300. , 693440
Publisher Maik Nauka Publishing / Springer SBM
Language of Original Document English
Abbreviated Source Title Autom. Remote Control
Source Scopus