Geodesic
On the sample monotonization problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 7, pp. 1327-1333 
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/
@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},
     year = {2010},
     volume = {50},
     number = {7},
     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
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
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_7_a13/
%G ru
%F ZVMMF_2010_50_7_a13

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.

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, 2, Mir, M., 1991

[3] Khachiyan L. G., “Polinomialnyi algoritm v lineinom programmirovanii”, Dokl. AN SSSR, 244 (1979), 1093–1096 | MR | Zbl

[4] Cook S. A., “The complexity of theorem proving procedures”, Proc. 3rd ACM Symp. Theory Comput., 1971

[5] Edmonds J., Karp R. M., “Theoretical improvements in algorithmic efficiency for network flow problems”, J. ACM, 19:2 (1972), 248–264 | DOI | Zbl

[6] Grotshel M., Lovasz L., Schrijver A., Geometric algorithms and combinatorial optimization, Springer, Berlin etc., 1988 | MR

[7] Hochbaum D. S., “Approximation algorithms for the set covering and vertex cover problems”, SIAM J. Comput., 11 (1982), 555–556 | DOI | MR | Zbl

[8] Mohring R. H., “Algorithmic aspects of comparability graphs and interval graphs”, Graphs and Order, 1985, 41–101 | MR