On the sample monotonization problem

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)1260-1266
Number of pages7
JournalComputational Mathematics and Mathematical Physics
Volume50
Issue number7
DOIs
Publication statusPublished - Aug 3 2010

Keywords

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

ASJC Scopus subject areas

  • Computational Mathematics

Fingerprint Dive into the research topics of 'On the sample monotonization problem'. Together they form a unique fingerprint.

Cite this