Geodesic
Complexity of partial inverse assignment problem and partial inverse cut problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 1, pp. 117-126 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Classification : 68Q25, 90B10, 90C27
Keywords: partial inverse assignment problem, partial inverse minimum cut problem, NP-hard 
@article{RO_2001__35_1_117_0,
     author = {Yang, Xiaoguang},
     title = {Complexity of partial inverse assignment problem and partial inverse cut problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {117--126},
     year = {2001},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {1},
     mrnumber = {1841816},
     zbl = {0993.90068},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RO_2001__35_1_117_0/}
}
TY  - JOUR
AU  - Yang, Xiaoguang
TI  - Complexity of partial inverse assignment problem and partial inverse cut problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
SP  - 117
EP  - 126
VL  - 35
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/RO_2001__35_1_117_0/
LA  - en
ID  - RO_2001__35_1_117_0
ER  - 
%0 Journal Article
%A Yang, Xiaoguang
%T Complexity of partial inverse assignment problem and partial inverse cut problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 117-126
%V 35
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/RO_2001__35_1_117_0/
%G en
%F RO_2001__35_1_117_0
Yang, Xiaoguang. Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 1, pp. 117-126. http://geodesic.mathdoc.fr/item/RO_2001__35_1_117_0/