# Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

RAIRO - Operations Research (2010)

- Volume: 35, Issue: 1, page 117-126
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topYang, Xiaoguang. "Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem." RAIRO - Operations Research 35.1 (2010): 117-126. <http://eudml.org/doc/197788>.

@article{Yang2010,

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.
},

author = {Yang, Xiaoguang},

journal = {RAIRO - Operations Research},

keywords = {Partial inverse assignment problem; partial
inverse minimum cut problem; NP–hard.; partial inverse assignment problem; partial inverse minimum cut problem; NP-hard},

language = {eng},

month = {3},

number = {1},

pages = {117-126},

publisher = {EDP Sciences},

title = {Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem},

url = {http://eudml.org/doc/197788},

volume = {35},

year = {2010},

}

TY - JOUR

AU - Yang, Xiaoguang

TI - Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

JO - RAIRO - Operations Research

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 1

SP - 117

EP - 126

AB - 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.

LA - eng

KW - Partial inverse assignment problem; partial
inverse minimum cut problem; NP–hard.; partial inverse assignment problem; partial inverse minimum cut problem; NP-hard

UR - http://eudml.org/doc/197788

ER -

## References

top- 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).
- 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).
- 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).
- M. Cai, X. Yang and Y. Li, Inverse polymatroidal flow problem. J. Comb. Optim.3 (1999) 115-126.
- M. Cai, X. Yang and Y. Li, Inverse problems of submodular functions on digraphs. J. Optim. Theory Appl.104 (2000) 559-575.
- M. Cai, X. Yang and J. Zhang, Inverse problems with partial given solution, Working Paper. Department of Mathematics, City University of Hong Kong (1997).
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide of the Theory of NP-Completeness. Freeman, San Francisco (1979).
- C. Yang and J. Zhang, Inverse maximum flow and minimum cut problems. Optimization40 (1997) 147-170.
- J. Zhang and M. Cai, Inverse problem of minimum cuts. ZOR-Math. Methods Oper. Res.48 (1998) 51-58.
- J. Zhang and Z. Ma, A network flow method for solving some inverse combinatorial optimization problems. Optimization37 (1996) 59-72.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.