Article ID: | iaor20053291 |
Country: | France |
Volume: | 35 |
Issue: | 1 |
Start Page Number: | 117 |
End Page Number: | 126 |
Publication Date: | Jan 2001 |
Journal: | RAIRO Operations Research |
Authors: | Yang Xiaoguang |
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.