Geodesic
On the sample monotonization problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1327-1333

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of finding a maximal subsample in a training sample consisting of the pairs “object-answer” that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed. 
@article{ZVMMF_2010_50_7_a13,
     author = {R. S. Takhanov},
     title = {On the sample monotonization problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1327--1333},
     publisher = {mathdoc},
     volume = {50},
     number = {7},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a13/}
}
TY  - JOUR
AU  - R. S. Takhanov
TI  - On the sample monotonization problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 1327
EP  - 1333
VL  - 50
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a13/
LA  - ru
ID  - ZVMMF_2010_50_7_a13
ER  - 
%0 Journal Article
%A R. S. Takhanov
%T On the sample monotonization problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 1327-1333
%V 50
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a13/
%G ru
%F ZVMMF_2010_50_7_a13
R. S. Takhanov. On the sample monotonization problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1327-1333. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a13/