Some lower bounds for the complexity of the linear programming feasibility problem over the reals

DOI10.1016/J.JCO.2008.07.002MaRDI QIDQ998976zbMATH OpenOpenAlexFDO

Authors Rafael Grimson, Bart Kuijpers

Publication date 30 January 2009

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

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

zbMATH Keywords

linear programmingalgebraic complexitycomplexity lower boundspolyhedra and polytopeslimiting hypersurface

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Linear programming (90C05)

Recommendations

• On the complexity of linear programming in the BSS-model
• Improved complexity results on solving real-number linear feasibility problems
• Lower bounds for parallel linear programming and other problems
• Polynomial algorithms for linear programming over the algebraic numbers
• scientific article; zbMATH DE number 3858831

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 4154416 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3564960 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1984321 (Why is no real title available?)
• scientific article; zbMATH DE number 1500505 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Constraint Databases
• Factoring bivariate sparse (lacunary) polynomials
• Kronecker's smart, little black boxes
• Linear optimization and extensions
• Lower bounds for arithmetic networks
• Mathematical problems of the next century
• On the Theoretical and Practical Complexity of the Existential Theory of Reals
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the intrinsic complexity of elimination theory
• Quantifier elimination: Optimal solution for two classical examples
• Real quantifier elimination is doubly exponential
• Semi-algebraic decision complexity, the real spectrum, and degree
• Solving systems of polynomial inequalities in subexponential time
• The Computational Complexity of Continued Fractions
• The complexity of linear problems in fields
• The complexity of quantifier elimination and cylindrical algebraic decomposition
• The hardness of polynomial equation solving
• The intrinsic complexity of parametric elimination methods

Cited in

(5)

• Lower bounds for parallel linear programming and other problems
• Exact algorithms for linear programming over algebraic extensions
• scientific article; zbMATH DE number 3858831 (Why is no real title available?)
• scientific article; zbMATH DE number 3952498 (Why is no real title available?)
• Improved complexity results on solving real-number linear feasibility problems

This page was built for publication: Some lower bounds for the complexity of the linear programming feasibility problem over the reals

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