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

DOI10.1016/J.JCO.2008.07.002zbMATH Open1171.65045OpenAlexW1996324240MaRDI QIDQ998976FDOQ998976

Bart Kuijpers, Rafael Grimson

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

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

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)

Cites Work

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

Cited In (4)

• Exact algorithms for linear programming over algebraic extensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)