Geodesic
The unsolvability of vector discrete optimization problems in a class of algorithms of a linear convolution of criteria
Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 89-96

Voir la notice de l'article provenant de la source Math-Net.Ru

In terms of systems of subsets, we describe a rather wide class of problems on combinatorial vector optimization which are unsolvable by the classical technique of linear convolution of criteria. This class includes, in particular, some well-known problems on graphs (the travelling salesman problem, the problem on a path between vertices and perfect matching problem, the problem on $p$-median and the problem on covering a graph by paths) as well as various Boolean programming problems with vector-valued criterion function being an arbitrary combination of criteria of the form $\maxsum$, $\maxmin$, $\maxmax$.This work was partially supported by the Foundation for Basic Researches of the Republic of Byelorussia. 
@article{DM_1996_8_2_a5,
     author = {M. K. Kravtsov},
     title = {The unsolvability of vector discrete optimization problems in a class of algorithms of a linear convolution of criteria},
     journal = {Diskretnaya Matematika},
     pages = {89--96},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {1996},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1996_8_2_a5/}
}
TY  - JOUR
AU  - M. K. Kravtsov
TI  - The unsolvability of vector discrete optimization problems in a class of algorithms of a linear convolution of criteria
JO  - Diskretnaya Matematika
PY  - 1996
SP  - 89
EP  - 96
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1996_8_2_a5/
LA  - ru
ID  - DM_1996_8_2_a5
ER  - 
%0 Journal Article
%A M. K. Kravtsov
%T The unsolvability of vector discrete optimization problems in a class of algorithms of a linear convolution of criteria
%J Diskretnaya Matematika
%D 1996
%P 89-96
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1996_8_2_a5/
%G ru
%F DM_1996_8_2_a5
M. K. Kravtsov. The unsolvability of vector discrete optimization problems in a class of algorithms of a linear convolution of criteria. Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 89-96. http://geodesic.mathdoc.fr/item/DM_1996_8_2_a5/