Solvability of a class of discrete vector problems by the algorithms of linear convolution of criteria (Q1569405)

The possibility of application of the algorithm of linear convolution of criteria (ALCC) for the determination of the Pareto set in multicriteria trajectory minimization problems with one arbitrary and several ``bottleneck'' criteria is investigated. An algorithm is proposed that allows one to reduce any such problem to a problem with the same Pareto set, which can be solved by the ALCC. Examples are presented when the estimate of the complexity of the reduction is polynomial with respect to the dimension of the problem.