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

DOI10.1007/BF02592072zbMATH Open0636.90054MaRDI QIDQ3777792FDOQ3777792

Authors: Guy de Ghellinck, Jean-Philippe Vial 

Publication date: 1987

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

Recommendations

• An extension of Karmarkar's algorithm for linear programming using dual variables
• A Deterministic Kaczmarz Algorithm for Solving Linear Systems
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An implementation of Karmarkar's algorithm for linear programming
• scientific article; zbMATH DE number 1135749
• scientific article
• An extension of the simplex algorithm for semi-infinite linear programming
• scientific article; zbMATH DE number 892328
• scientific article; zbMATH DE number 4072277
• scientific article; zbMATH DE number 4082856

zbMATH Keywords

projective geometrypolynomial algorithmfeasibility problemsystem of linear homogeneous equationsKarmarkar's algorithm

Mathematics Subject Classification ID

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

Cites Work

• 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
• A monotonic projective algorithm for fractional linear programming
• Khachiyan's linear programming algorithm

Cited In (12)

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

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

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