On the multicriterial problem of the search for optimal sources in a graph (Q2736212)

The paper deals with a question of locating the Pareto set of a multicriteria optimization problem in the case when the set of admissible solutions is a vertex set of a tree. It turns out that certain conditions (e.g. monotonicity) on objective function permit to avoid full enumeration approach, and allow describing explicitly the corresponding polynomial algorithm. It has been shown that these conditions hold true whenever the partial objective functions are such functionals whose minimum one seeks in the problems of locating medians and centers in the graph. The time complexity of algorithm is estimated. The paper is addressed to researchers and engineers working in the area of multicriteria optimization.