On the inverse problem of linear programming and its application to minimum weight perfect k-matching

被引：16

作者：

Huang, SM ^{[1
]}

Liu, ZH

机构：

[1] Acad Sinica, Inst Policy & Management, Beijing 100080, Peoples R China

[2] Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1999年 / 112卷 / 02期

关键词：

linear programming; inverse problem; bipartite graph; strongly polynomial algorithm;

D O I：

10.1016/S0377-2217(97)00444-X

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We first introduce the inverse problem of linear programming. We then apply it to the inverse problem of minimum weight perfect k-matching of bipartite graphs. We show that there is a strongly polynomial algorithm for solving the problem. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：421 / 426

页数：6

共 9 条

[1]

Ahuja RK., 1993, NETWORK FLOWS THEORY

[2] ON THE USE OF AN INVERSE SHORTEST PATHS ALGORITHM FOR RECOVERING LINEARLY CORRELATED COSTS [J].

BURTON, D ;

TOINT, PL .

MATHEMATICAL PROGRAMMING, 1994, 63 (01) :1-22

[3] ON AN INSTANCE OF THE INVERSE SHORTEST PATHS PROBLEM [J].

BURTON, D ;

TOINT, PL .

MATHEMATICAL PROGRAMMING, 1992, 53 (01) :45-61

[4]

BURTON D, 1994, INVERSE SHORTEST PAT

[5] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[6]

HU Z, STRONGLY POLYNOMIAL

[7]

Kuhn H. W., 1956, Naval Research Logistics Quarterly, V3, P253, DOI [10.1002/nav.3800030404, DOI 10.1002/NAV.3800030404]

[8]

MA ZF, INVERSE COMBINATORIA

[9] A STRONGLY POLYNOMIAL ALGORITHM TO SOLVE COMBINATORIAL LINEAR-PROGRAMS [J].

TARDOS, E .

OPERATIONS RESEARCH, 1986, 34 (02) :250-256

← 1 →