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

• 成果类型: Article
• 署名作者: ADLER, I; COSARES, S
• 署名单位: Telcordia Technologies
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.6.955
• 发表日期: 1991
• 页码: 955-960
• 关键词: programming; LINEAR; STRONG POLYNOMALITY; EXPLOITING SPECIAL STRUCTURE

摘要

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.