О многокритериальной задаче поиска оптимальных источников в графе

Abstract

We consider the task of locating the Pareto set of a multicriteria optimization problem in the case when the set of admissible solutions is the vertex set of a tree. It turns out that certain conditions on the object function permit to avoid item-by-item examination, and we explicitly describe the corresponding polynomial algorithm. We then show that these conditions hold true whenever the partial optimality criteria reduce to functionals whose minimum one seeks in the problems of locating medians and centers in a graph. We estimate the time complexity of our algorithm.

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