On the complexity of linear programming under finite precision arithmetic

DOI10.1007/BF01582132zbMath0894.90112OpenAlexW2039868808MaRDI QIDQ1380938

Jorge R. Vera

Publication date: 11 March 1998

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

error analysisconditioninginterior point methodsfinite precision arithmeticlogarithmic barrier methodcomputing error bounds

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Error analysis and interval analysis (65G99)

Related Items (7)

A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Round-off estimates for second-order conic feasibility problems ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ Solving linear programs with finite precision. II: Algorithms ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Probabilistic analysis of the Grassmann condition number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior-point methods for convex programming
• On the classical logarithmic barrier function method for a class of smooth convex programming problems
• Some perturbation theory for linear programming
• Linear programming, complexity theory and elementary functional analysis
• Some Remarks on the Foundations of Numerical Analysis
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs

This page was built for publication: On the complexity of linear programming under finite precision arithmetic