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
Voir la notice de l'article provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {19},
number = {2},
year = {2013},
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 PB - mathdoc 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 %I mathdoc %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/