О задачах векторной дискретной оптимизации на системах подмножеств, неразрешимых с помощью алгоритмов линейной свертки

Доказано, что многокритериальные задачи на графах (коммивояжера, об остовных деревьях и цепях между двумя вершинами, о совершенных паросочетаниях и $p$-медиане, о покрытии графа цепями, звездами и циклами), а также разнообразные целочисленные задачи транспортного типа с векторной целевой функцией, представляющей собой любую комбинацию критериев вида MINMAX и MINSUM, неразрешимы с помощью алгоритмов линейной свертки критериев.