Том 8, серия 1, номер 2, 2001 г., Стр. 63-89

УДК 519.816
Л. А. Шоломов
Разделительная декомпозиция отношений в задачах многокритериального выбора

Аннотация:
Исследуются алгоритмические проблемы, связанные с разделительной декомпозицией отношений в задачах многокритериального выбора, т.е. с возможностью разбиения множества критериев $I$ на подмножества $I_1,\dots,I_k$ и представления выбора по заданному отношению $\rho$ на $I$ в виде последовательного выбора по некоторым отношениям $\rho_1,\dots,\rho_k$, заданным соответственно на $I_1,\dots,I_k$. Отношения предполагаются порядковыми и описываются функциями $(3,2)$-значной логики. Доказывается, что всякое отношение обладает лучшей разделительной декомпозицией, которая единственна с точностью до некоторого преобразования. При задании представляющих функций отношений в форме ДНФ и КНФ задачи о существовании нетривиальных декомпозиций и о построении лучших декомпозиций NP-трудны. Если отношения обладают свойством монотонности, то в случае ДНФ эти задачи остаются NP-трудными, а при задании в виде КНФ полиномиально разрешимы.
Библиогр. 13.

Шоломов Л. А. ¹
1. Институт системного анализа РАН,
пр. 60-летия Октября, 9, 117312 Москва, Россия
е-mail: sholomov@cs.isa.ac.ru

Статья поступила 21 ноября 2000 г.