Solving linear programs with finite precision. II: Algorithms

DOI10.1016/J.JCO.2005.10.001MaRDI QIDQ2496177zbMATH OpenOpenAlexWikidataFDO

Authors Dennis Cheung, Felipe Cucker

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)

Recommendations

• Solving linear programs with finite precision. I: Condition numbers and random programs
• On the complexity of linear programming under finite precision arithmetic
• On Linear Semi-Infinite Programming Problems: An Algorithm
• scientific article; zbMATH DE number 4066615
• A New Finite Continuation Algorithm for Linear Programming
• A finite algorithm for the least two-norm solution of a linear program¹
• scientific article; zbMATH DE number 3188095
• Exact algorithms for linear programming over algebraic extensions

Cites work

• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 1024452 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 3276117 (Why is no real title available?)
• A Characterization of Stability in Linear Programming
• A new condition number for linear programming
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• A stabilization of the simplex method
• Computing approximate solutions for convex conic systems of constraints
• Condition measures and properties of the central trajectory of a linear program
• Condition numbers for polyhedra with real number data
• Error control in the simplex-technique
• Extensions and Applications of the Householder Algorithm for Solving Linear Least Squares Problems
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Linear programming, complexity theory and elementary functional analysis
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the complexity of linear programming under finite precision arithmetic
• Solving linear programs with finite precision. I: Condition numbers and random programs
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• Techniques for automatic tolerance control in linear programming
• The simplex method is not always well behaved
• Unifying Condition Numbers for Linear Programming

Cited in

(11)

• Flyspeck II: The basic linear programs
• A numerical algorithm for zero counting. I: Complexity and accuracy
• A primal-dual symmetric relaxation for homogeneous conic systems
• A hybrid branch-and-bound approach for exact rational mixed-integer programming
• Round-off estimates for second-order conic feasibility problems
• Probabilistic analyses of condition numbers
• Solving Linear Problems with Finite Precision III: Sharp Expectation Bounds
• Solving second-order conic systems with variable precision
• Computing the homology of real projective sets
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• A New Finite Continuation Algorithm for Linear Programming

Describes a project that uses

Uses Software

• mctoolbox

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

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