Complexity of partial inverse assignment problem and partial inverse cut problem

Complexity of partial inverse assignment problem and partial inverse cut problem

0.00 Avg rating0 Votes
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:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.