A Strongly Polynomial Algorithm for a Special Class of Linear Programs

DOI10.1287/OPRE.39.6.955MaRDI QIDQ4006338zbMATH OpenOpenAlexFDO

Authors Ilan Adler, Steven Cosares

Publication date 26 September 1992

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/03c7de834783a0d9812c093af176eaceb85b2957

zbMATH Keywords

strongly polynomial timeLeontief substitution systemsgeneralized transshipment

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A strongly polynomial algorithm for linear systems having a binary solution
• A simplex algorithm for a class of Leontief flow problems
• A strongly polynomial time algorithm for an LP problem with a pre-Leontief coefficient matrix

Cited in

(19)

• A strongly polynomial algorithm for linear systems having a binary solution
• A combinatorial certifying algorithm for linear programming problems with gainfree Leontief substitution systems
• New algorithms for generalized network flows
• Minimizing convex functions with rational minimizers
• Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
• Complete Algorithms for Algebraic Strongest Postconditions and Weakest Preconditions in Polynomial ODE’S
• A strongly polynomial algorithm for bimodular integer linear programming
• Deepest point of a polyhedron and linear programming
• An efficient algorithm for solving a special class of LP's
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• A strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial time algorithm for an LP problem with a pre-Leontief coefficient matrix
• scientific article; zbMATH DE number 1083133 (Why is no real title available?)
• Reformulation of the linear program for completely ergodic MDPs with average cost criteria
• A linear programming primer: from Fourier to Karmarkar
• Gainfree Leontief substitution flow problems
• An -relaxation method for generalized separable convex cost network flow problems
• Monotonizing linear programs with up to two nonzeroes per column

This page was built for publication: A Strongly Polynomial Algorithm for a Special Class of Linear Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4006338)