Solving linear programs with finite precision. II: Algorithms

DOI10.1016/j.jco.2005.10.001zbMath1105.90042OpenAlexW2090722933WikidataQ57733196 ScholiaQ57733196MaRDI QIDQ2496177

Felipe Cucker, Dennis Cheung

Publication date: 12 July 2006

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2005.10.001

zbMATH Keywords

linear programmingconditioningfinite precision

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (7)

A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Round-off estimates for second-order conic feasibility problems ⋮ Computing the homology of real projective sets ⋮ A numerical algorithm for zero counting. I: Complexity and accuracy ⋮ Probabilistic analyses of condition numbers ⋮ Linear programming using limited-precision oracles ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming

Uses Software

• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The simplex method is not always well behaved
• Condition measures and properties of the central trajectory of a linear program
• On the complexity of linear programming under finite precision arithmetic
• Solving linear programs with finite precision. I: Condition numbers and random programs
• Computing approximate solutions for convex conic systems of constraints
• Linear programming, complexity theory and elementary functional analysis
• Condition numbers for polyhedra with real number data
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• A stabilization of the simplex method
• A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
• A Characterization of Stability in Linear Programming
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Error control in the simplex-technique
• Techniques for automatic tolerance control in linear programming
• Extensions and Applications of the Householder Algorithm for Solving Linear Least Squares Problems
• Unifying Condition Numbers for Linear Programming
• A new condition number for linear programming

This page was built for publication: Solving linear programs with finite precision. II: Algorithms