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.

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
Mots clés : 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},
publisher = {EDP-Sciences},
volume = {35},
number = {1},
year = {2001},
zbl = {0993.90068},
mrnumber = {1841816},
language = {en},
url = {http://www.numdam.org/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
DA  - 2001///
SP  - 117
EP  - 126
VL  - 35
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_1_117_0/
UR  - https://zbmath.org/?q=an%3A0993.90068
UR  - https://www.ams.org/mathscinet-getitem?mr=1841816
LA  - en
ID  - RO_2001__35_1_117_0
ER  - 
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://www.numdam.org/item/RO_2001__35_1_117_0/

[1] R.K. Ahuja and J.B. Orlin, Inverse optimization, Part I: Linear programming and general problems, Working Paper, SWP#4002. Sloan School of Management, MIT, Cambridge, MA (1998).

[2] R.K. Ahuja and J.B. Orlin, Inverse optimization, Part II: Network flow problems, Working Paper, SWP#4003. Sloan School of Management, MIT, Cambridge, MA (1998).

[3] R.K. Ahuja and J.B. Orlin, Combinatorial algorithms for inverse network flow problems, Working Paper, SWP#4004. Sloan School of Management, MIT, Cambridge, MA (1998).

[4] M. Cai, X. Yang and Y. Li, Inverse polymatroidal flow problem. J. Comb. Optim. 3 (1999) 115-126. | MR 1702524 | Zbl 0957.90126

[5] M. Cai, X. Yang and Y. Li, Inverse problems of submodular functions on digraphs. J. Optim. Theory Appl. 104 (2000) 559-575. | MR 1760738 | Zbl 1034.90012

[6] M. Cai, X. Yang and J. Zhang, Inverse problems with partial given solution, Working Paper. Department of Mathematics, City University of Hong Kong (1997).

[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide of the Theory of NP-Completeness. Freeman, San Francisco (1979). | MR 519066 | Zbl 0411.68039

[8] C. Yang and J. Zhang, Inverse maximum flow and minimum cut problems. Optimization 40 (1997) 147-170. | MR 1620376 | Zbl 0880.90041

[9] J. Zhang and M. Cai, Inverse problem of minimum cuts. ZOR-Math. Methods Oper. Res. 48 (1998) 51-58. | MR 1612508 | Zbl 0941.90013

[10] J. Zhang and Z. Ma, A network flow method for solving some inverse combinatorial optimization problems. Optimization 37 (1996) 59-72. | MR 1419272 | Zbl 0866.90099