On the complexity of linear programming under finite precision arithmetic

DOI10.1007/BF01582132zbMATH Open0894.90112OpenAlexW2039868808MaRDI QIDQ1380938FDOQ1380938

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

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

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)

Cites Work

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

Cited In (16)

• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• Probabilistic analysis of the Grassmann condition number
• Title not available (Why is that?)
• On the complexity of linear programming in the BSS-model
• Probabilistic analysis of condition numbers for linear programming
• 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
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• 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)