О задаче монотонизации выборки

Рассматривается задача выделения максимальной подвыборки некоторой обучающей выборки, состоящей из пар вида "объект-ответ", не противоречащей ограничениям монотонности. Показывается, что данная задача является NP-трудной и равносильна задаче о максимальном независимом множестве в специальных орграфах. Подробно рассматриваются практически важные случаи, когда частичный порядок, заданный на множестве ответов, является полным порядком либо имеет размерность 2. Показывается, что второй случай сводится к максимизации квадратично-выпуклой функции на выпуклом множестве. Для этого случая строится приближенный полиномиальный алгоритм, основанный на линейном программировании. Библ. 8.