A STRONGLY POLYNOMIAL ALGORITHM FOR A SPECIAL-CLASS OF LINEAR-PROGRAMS

被引：19

作者：

ADLER, I ^{[1
]}

COSARES, S ^{[1
]}

机构：

[1] BELL COMMUN RES INC,TECH STAFF,PISCATAWAY,NJ

来源：

OPERATIONS RESEARCH | 1991年 / 39卷 / 06期

关键词：

PROGRAMMING; LINEAR; STRONG POLYNOMALITY; EXPLOITING SPECIAL STRUCTURE;

D O I：

10.1287/opre.39.6.955

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We extend the list of linear programming problems that are known to be solvable in strongly polynomial time to include a class of LPs which contains special cases of the generalized transshipment problem. The result is facilitated by exploiting some special properties associated with Leontief substitution systems and observing that a feasible solution to the system, Ax = b, x greater-than-or-equal-to 0, in which no variable appears in more than two equations, can be found in strongly polynomial time for b belonging to some set-OMEGA.

引用

页码：955 / 960

页数：6

共 17 条

[1]

ADLER I, 1989, NESTED PARAMETERIZED

[2] A POLYNOMIAL TIME ALGORITHM FOR SOLVING SYSTEMS OF LINEAR INEQUALITIES WITH 2 VARIABLES PER INEQUALITY [J].