Complexity of partial inverse assignment problem and partial inverse cut problem

被引:16
作者
Yang, XG [1 ]
机构
[1] Chinese Acad Sci, Inst Syst Sci, Lab Management Decis & Informat Syst, Beijing 100080, Peoples R China
来源
RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH | 2001年 / 35卷 / 01期
关键词
partial inverse assignment problem; partial inverse minimum cut problem; NP-hard;
D O I
10.1051/ro:2001106
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:117 / 126
页数:10
相关论文
共 10 条
[1]  
AHUJA RK, 1998, 4002 SWP MIT SLOAN S
[2]  
AHUJA RK, 1998, 4004 SWP MIT SLOAN S
[3]  
AHUJA RK, 1998, 4003 SWP MIT SLOAN S
[4]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[5]   Inverse problems of submodular functions on digraphs [J].
Cai, M ;
Yang, X ;
Li, Y .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2000, 104 (03) :559-575
[6]  
CAI M, 1997, INVERSE PROBLEMS PAR
[7]   Inverse polymatroidal flow problem [J].
Cai, MC ;
Yang, XG ;
Li, YJ .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 1999, 3 (01) :115-126
[8]  
Yang C, 1997, OPTIMIZATION, V40, P147, DOI DOI 10.1080/02331939708844306
[9]  
ZHANG J, 1996, OPTIMIZATION, V37, P59
[10]   Inverse problem of minimum cuts [J].
Zhang, JZ ;
Cai, MC .
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 1998, 47 (01) :51-58