Issue |
RAIRO-Oper. Res.
Volume 35, Number 1, January March 2001
|
|
---|---|---|
Page(s) | 117 - 126 | |
DOI | https://doi.org/10.1051/ro:2001106 | |
Published online | 15 August 2002 |
Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
Laboratory of Management, Decision and Information Systems,
Institute of Systems Science, Chinese Academy of Sciences,
Beijing 100080, P.R. China; xgyang@iss04.iss.ac.cn.
Received:
February
2000
Accepted:
January
2001
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.
Mathematics Subject Classification: 68Q25 / 90B10 / 90C27
Key words: Partial inverse assignment problem / partial inverse minimum cut problem / NP–hard.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.