The partial inverse minimum cut problem with L1-norm is strongly NP-hard
RAIRO - Operations Research (2010)
- Volume: 44, Issue: 3, page 241-249
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topGassner, Elisabeth. "The partial inverse minimum cut problem with L1-norm is strongly NP-hard." RAIRO - Operations Research 44.3 (2010): 241-249. <http://eudml.org/doc/250836>.
@article{Gassner2010,
abstract = {
The partial inverse minimum cut problem is to minimally
modify the capacities of a digraph such that
there exists a minimum cut with respect to the new capacities that
contains all arcs of a prespecified set. Orlin showed that the problem is
strongly NP-hard if the amount of
modification is measured by the weighted L1-norm. We prove that the problem
remains hard for the unweighted case and show that the
NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional
bound constraints is not
correct.
},
author = {Gassner, Elisabeth},
journal = {RAIRO - Operations Research},
keywords = {Partial inverse minimum cut problem; partial inverse minimum cut problem},
language = {eng},
month = {10},
number = {3},
pages = {241-249},
publisher = {EDP Sciences},
title = {The partial inverse minimum cut problem with L1-norm is strongly NP-hard},
url = {http://eudml.org/doc/250836},
volume = {44},
year = {2010},
}
TY - JOUR
AU - Gassner, Elisabeth
TI - The partial inverse minimum cut problem with L1-norm is strongly NP-hard
JO - RAIRO - Operations Research
DA - 2010/10//
PB - EDP Sciences
VL - 44
IS - 3
SP - 241
EP - 249
AB -
The partial inverse minimum cut problem is to minimally
modify the capacities of a digraph such that
there exists a minimum cut with respect to the new capacities that
contains all arcs of a prespecified set. Orlin showed that the problem is
strongly NP-hard if the amount of
modification is measured by the weighted L1-norm. We prove that the problem
remains hard for the unweighted case and show that the
NP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additional
bound constraints is not
correct.
LA - eng
KW - Partial inverse minimum cut problem; partial inverse minimum cut problem
UR - http://eudml.org/doc/250836
ER -
References
top- R.K. Ahuja and J.B. Orlin, Inverse optimization. Oper. Res.49 (2001) 771–783.
- L.R. Ford, Jr. and D.R. Fulkerson, Maximal flow through a network. Canad. J. Math.8 (1956) 399–404.
- M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci.1 (1976) 237–267.
- C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods, and results. J. Comb. Optim.8 (2004) 329–361.
- T.C. Lai and J.B. Orlin, The complexity of preprocessing. Research Report of Sloan School of Management, MIT (2003).
- J.B. Orlin, Partial inverse optimization problems. Working paper, Sloan School of Management, MIT.
- X. Yang, Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO-Oper. Res.35 (2001) 117–126.
- J. Zhang and M.-C. Cai, Inverse problem of minimum cuts. Math. Methods Oper. Res.47 (1998) 51–58.
NotesEmbed ?
topYou 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.