Сложность дискретных многокритериальных задач

Обзор содержит результаты, касающиеся оценок вычислительной сложности комбинаторных задач векторной оптимизации, разрешимости этих задач в классе алгоритмов линейной свертки, обоснованию точности быстрых алгоритмов нахождения множества альтернатив в типичном случае. Рассматриваемые дискретные многокритериальные задачи охватывают основную часть шкалы оценок вычислительной сложности: полиномиально разрешимые, полиномиально сводимые к классу NP и труднорешаемые.
Эта работа частично финансировалась Фондом фундаментальных исследований Республики Беларусь.