On the complexity of linear programming under finite precision arithmetic

DOI10.1007/BF01582132MaRDI QIDQ1380938zbMATH OpenOpenAlexFDO

Authors 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

interior point methodserror analysisconditioningfinite precision arithmeticlogarithmic barrier methodcomputing error bounds

Mathematics Subject Classification ID

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

Recommendations

• Solving linear programs with finite precision. II: Algorithms
• scientific article; zbMATH DE number 1008382
• Solving linear programs with finite precision. I: Condition numbers and random programs
• Incorporating Condition Measures into the Complexity Theory of Linear Programming

Cites work

• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Interior-point methods for convex programming
• Linear programming, complexity theory and elementary functional analysis
• On the classical logarithmic barrier function method for a class of smooth convex programming problems
• Some Remarks on the Foundations of Numerical Analysis
• Some perturbation theory for linear programming

Cited in

(16)

• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• Probabilistic analysis of the Grassmann condition number
• scientific article; zbMATH DE number 2109417 (Why is no real title available?)
• Probabilistic analysis of condition numbers for linear programming
• On the complexity of linear programming in the BSS-model
• A primal-dual symmetric relaxation for homogeneous conic systems
• On the computational hardness based on linear fpt-reductions
• Linear FPT reductions and computational lower bounds
• A hybrid branch-and-bound approach for exact rational mixed-integer programming
• Round-off estimates for second-order conic feasibility problems
• Pushing the Envelope of Optimization Modulo Theories with Linear-Arithmetic Cost Functions
• On the efficient use of the architecture of a small computer for LP algorithms
• Solving linear programs with finite precision. II: Algorithms
• Improved complexity results on solving real-number linear feasibility problems
• Some aspects of studying an optimization or decision problem in different computational models

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

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