Complexity of partial inverse assignment problem and partial inverse cut problem

Xiaoguang Yang

RAIRO - Operations Research - Recherche Opérationnelle (2001)

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

Abstract

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

How to cite

top

Yang, Xiaoguang. "Complexity of partial inverse assignment problem and partial inverse cut problem." RAIRO - Operations Research - Recherche Opérationnelle 35.1 (2001): 117-126. <http://eudml.org/doc/105233>.

@article{Yang2001,
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 - Recherche Opérationnelle},
keywords = {partial inverse assignment problem; partial inverse minimum cut problem; NP–hard; NP-hard},
language = {eng},
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/105233},
volume = {35},
year = {2001},
}

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
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; NP-hard
UR - http://eudml.org/doc/105233
ER -

References

top
  1. [1] 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). 
  2. [2] 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). 
  3. [3] 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). 
  4. [4] M. Cai, X. Yang and Y. Li, Inverse polymatroidal flow problem. J. Comb. Optim. 3 (1999) 115-126. Zbl0957.90126MR1702524
  5. [5] M. Cai, X. Yang and Y. Li, Inverse problems of submodular functions on digraphs. J. Optim. Theory Appl. 104 (2000) 559-575. Zbl1034.90012MR1760738
  6. [6] M. Cai, X. Yang and J. Zhang, Inverse problems with partial given solution, Working Paper. Department of Mathematics, City University of Hong Kong (1997). 
  7. [7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide of the Theory of NP-Completeness. Freeman, San Francisco (1979). Zbl0411.68039MR519066
  8. [8] C. Yang and J. Zhang, Inverse maximum flow and minimum cut problems. Optimization 40 (1997) 147-170. Zbl0880.90041MR1620376
  9. [9] J. Zhang and M. Cai, Inverse problem of minimum cuts. ZOR–Math. Methods Oper. Res. 48 (1998) 51-58. Zbl0941.90013
  10. [10] J. Zhang and Z. Ma, A network flow method for solving some inverse combinatorial optimization problems. Optimization 37 (1996) 59-72. Zbl0866.90099MR1419272

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.