Khachiyan’s algorithm for linear programming

DOI10.1007/BFb0120921zbMath0463.90066OpenAlexW1977733379MaRDI QIDQ3914757

Peter Gács

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 algorithmpolynomial algorithmlinear inequalities

Mathematics Subject Classification ID

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

Related Items (31)

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

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