An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex

DOI10.1007/BF02592072zbMath0636.90054MaRDI QIDQ3777792

Jean-Philippe Vial, Guy de Ghellinck

Publication date: 1987

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmprojective geometryfeasibility problemsystem of linear homogeneous equationsKarmarkar's algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items (10)

A polynomial Newton method for linear programming ⋮ A fully polynomial time projective method ⋮ Cutting planes and column generation techniques with the projective algorithm ⋮ Generalization of Karmarkar's algorithm to convex homogeneous functions ⋮ A projective algorithm for linear programming with no regularity condition ⋮ On combined phase 1-phase 2 projective methods for linear programming ⋮ Search directions for a class of projective methods ⋮ Linear updates for a single-phase projective method ⋮ El metodo de Karmarkar: Un estudio de sus variantes ⋮ Determination of an interior feasible point for a system of linear constraints

Cites Work

• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A polynomial Newton method for linear programming
• Khachiyan's linear programming algorithm

This page was built for publication: An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex