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.

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}, publisher = {EDP-Sciences}, volume = {35}, number = {1}, year = {2001}, mrnumber = {1841816}, zbl = {0993.90068}, language = {en}, url = {http://archive.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 SP - 117 EP - 126 VL - 35 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/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://archive.numdam.org/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, Volume 35 (2001) no. 1, pp. 117-126. http://archive.numdam.org/item/RO_2001__35_1_117_0/

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

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

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

and ,[4] Inverse polymatroidal flow problem. J. Comb. Optim. 3 (1999) 115-126. | MR | Zbl

, and ,[5] Inverse problems of submodular functions on digraphs. J. Optim. Theory Appl. 104 (2000) 559-575. | MR | Zbl

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

, and ,[7] Computers and Intractability: A Guide of the Theory of NP-Completeness. Freeman, San Francisco (1979). | MR | Zbl

and ,[8] Inverse maximum flow and minimum cut problems. Optimization 40 (1997) 147-170. | MR | Zbl

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

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

and ,