### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1260-1266 |

Number of pages | 7 |

Journal | Computational Mathematics and Mathematical Physics |

Volume | 50 |

Issue number | 7 |

DOIs | |

Publication status | Published - 2010 |

Externally published | Yes |

### Fingerprint

### Keywords

- Learning from precedents
- Monotone constraints
- NP-hard problem
- Sample monotonization

### ASJC Scopus subject areas

- Computational Mathematics

### Cite this

**On the sample monotonization problem.** / Takhanov, R. S.

Research output: Contribution to journal › Article

*Computational Mathematics and Mathematical Physics*, vol. 50, no. 7, pp. 1260-1266. https://doi.org/10.1134/S0965542510070146

}

TY - JOUR

T1 - On the sample monotonization problem

AU - Takhanov, R. S.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Learning from precedents

KW - Monotone constraints

KW - NP-hard problem

KW - Sample monotonization

UR - http://www.scopus.com/inward/record.url?scp=77955025004&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955025004&partnerID=8YFLogxK

U2 - 10.1134/S0965542510070146

DO - 10.1134/S0965542510070146

M3 - Article

VL - 50

SP - 1260

EP - 1266

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 7

ER -