Khachiyan’s algorithm for linear programming

DOI10.1007/BFB0120921MaRDI QIDQ3914757zbMATH OpenOpenAlexFDO

Authors Peter Gács, László Lovász

Publication date 1981

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

Full work available at URL https://doi.org/10.1007/bfb0120921

zbMATH Keywords

ellipsoid algorithmlinear inequalitiespolynomial algorithm

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Cited in

(32)

• The vertices of the knapsack polytope
• Neighborhood perfect graphs
• Complexity, convexity and combinations of theories
• On relaxation methods for systems of linear inequalities
• The ellipsoid method and its consequences in combinatorial optimization
• An appraisal of computational complexity for operations researchers
• Projection algorithms for linear programming
• Method of centers for minimizing generalized eigenvalues
• New iterative methods for linear inequalities
• Simplices by point-sliding and the Yamnitsky-Levin algorithm
• Approximation schemes for parallel machine scheduling with non-renewable resources
• Fast finite methods for a system of linear inequalities
• The ellipsoid method and its implications
• Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
• An exterior point polynomial-time algorithm for convex quadratic programming
• An entire space polynomial-time algorithm for linear programming
• Approximability of scheduling problems with resource consuming jobs
• Preface: Taming randomness and complexity -- essays in honour of Professor Péter Gács
• The sphere method and the robustness of the ellipsoid algorithm
• Fractional covers for forests and matchings
• Optimization problems with algebraic solutions: Quadratic fractional programs and ratio games
• A Variable-Complexity Norm Maximization Problem
• A finite algorithm for the continuousp-center location problem on a graph
• On Estimating Optimal Bases for Linear Programs
• Modifications and implementation of the ellipsoid algorithm for linear programming
• Even circuits in oriented matroids
• The history of the LLL-algorithm
• A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
• Interval graphs with side (and size) constraints
• A global pricing extension of the simplex method
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• The \(p\)-hub center allocation problem

This page was built for publication: Khachiyan’s algorithm for linear programming

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