Geodesic
Boosting and the polynomial approximability of the problem on a minimum affine separating committee
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 231-236 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We investigate the intractable problem on a minimum affine separating committee in a space of fixed dimension $n>1$ under the additional constraint that the separated sets are in general position (MASC-GP($n$)). For the investigation of the set of separable subsets that are maximal with respect to inclusion, we apply the game approach, which is traditional for boosting. We construct a polynomial approximate algorithm with guaranteed error estimate $O((m/n\ln m)^{1/2})$, where $m$ is the cardinality of the separated set.
Keywords: minimum affine separating committee problem, boosting, polynomial approximate algorithm, approximation error. 
@article{TIMM_2013_19_2_a21,
     author = {Vl. D. Mazurov and M. Yu. Khachai},
     title = {Boosting and the polynomial approximability of the problem on a~minimum affine separating committee},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {231--236},
     year = {2013},
     volume = {19},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a21/}
}
TY  - JOUR
AU  - Vl. D. Mazurov
AU  - M. Yu. Khachai
TI  - Boosting and the polynomial approximability of the problem on a minimum affine separating committee
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2013
SP  - 231
EP  - 236
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a21/
LA  - ru
ID  - TIMM_2013_19_2_a21
ER  - 
%0 Journal Article
%A Vl. D. Mazurov
%A M. Yu. Khachai
%T Boosting and the polynomial approximability of the problem on a minimum affine separating committee
%J Trudy Instituta matematiki i mehaniki
%D 2013
%P 231-236
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a21/
%G ru
%F TIMM_2013_19_2_a21
Vl. D. Mazurov; M. Yu. Khachai. Boosting and the polynomial approximability of the problem on a minimum affine separating committee. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 231-236. http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a21/

[1] Eremin I. I., Mazurov Vl. D., Astafev N. N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp. | MR

[2] Eremin I. I., Protivorechivye modeli optimalnogo planirovaniya, Nauka, M., 1988, 160 pp. | MR | Zbl

[3] Mazurov Vl. D., Metod komitetov v zadachakh optimizatsii i klassifikatsii, Nauka, M., 1990, 348 pp. | MR | Zbl

[4] Schapire R., Freund Y., Boosting, MitPress, 2012, 496 pp. | MR | Zbl

[5] Mazurov Vl. D., “Komitety sistem neravenstv i zadacha raspoznavaniya obrazov”, Kibernetika, 1971, no. 3, 140–146 | MR | Zbl

[6] Khachai M., “Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets”, Pattern Recognition and Image Analysis, 18:2 (2008), 237–242 | DOI

[7] Khachai M., Poberii M., “Complexity and approximability of committee polyhedral separability of sets in general position”, Informatica, 20:2 (2009), 217–234 | MR

[8] Khachai M., Mazurov V., Rybin A., “Committee construction for solving problems of selection, diagnostics, and prediction”, Proc. Steklov Inst. Math., Suppl. 1, 2002, S67–S101 | MR | Zbl

[9] Freund Y., “Boosting a weak algorithm by majority”, Information and Computation, 121 (1995), 256–285 | DOI | MR | Zbl

[10] Gainanov D. N., Novokshenov V. A., Tyagunov L. I., “O grafakh, porozhdaemykh nesovmestnymi sistemami lineinykh neravenstv”, Mat. zametki, 33:2 (1983), 293–300 | MR | Zbl

[11] Mazurov Vl. D., Khachai M. Yu., “Komitetnye konstruktsii”, Izv. Ural. gos. un-ta, 1999, no. 14, 76–108