## 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 - Aug 3 2010 |

## Keywords

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

## ASJC Scopus subject areas

- Computational Mathematics