On the non-polynomiality of the relaxation method for systems of linear inequalities

DOI10.1007/BF01581028zbMath0473.90051MaRDI QIDQ3929533

Jean-Louis Goffin

Publication date: 1982

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

zbMATH Keywords

polynomial algorithmellipsoid methodKhachiyan's algorithmnon-polynomialityrelaxation method for inequalities

Mathematics Subject Classification ID

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

Related Items

Solving the general quadratic programming problem in a finite number of steps, Strong convergence of expected-projection methods in hilbert spaces, On Chubanov's Method for Linear Programming, Locally polynomial method for solving systems of linear inequalities, A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility, A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem, Projection algorithms for linear programming, Convergence of the cyclical relaxation method for linear inequalities, A deterministic rescaled perceptron algorithm, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Convergence criteria for generalized gradient methods of solving locally Lipschitz feasibility problems, A polynomial algorithm for convex quadratic optimization subject to linear inequalities, A polynomial projection algorithm for linear feasibility problems, A projection method for least-squares solutions to overdetermined systems of linear inequalities, Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin, Method of Alternating Contractions and Its Applications to Some Convex Optimization Problems, Variable metric relaxation methods, part II: The ellipsoid method

Cites Work

• Unnamed Item
• Efficient search for rationals
• The Relaxation Method for Solving Systems of Linear Inequalities
• Convergence rate of the gradient descent method with dilatation of the space
• On Over and Under Relaxation in the Theory of the Cyclic Single Step Iteration
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities