Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs

DOI10.1137/S105262349223352XMaRDI QIDQ4895608zbMATH OpenFDO

Authors Jorge R. Vera

Publication date 3 February 1997

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S105262349223352X

zbMATH Keywords

approximate dataconditioningexistence of solutions

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Ill-posedness with respect to the solvability in linear optimization
• On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data
• Solving linear programs with finite precision. I: Condition numbers and random programs
• scientific article; zbMATH DE number 1099078
• scientific article; zbMATH DE number 1008382

Cited in

(17)

• On optimal zero-preserving corrections for inconsistent linear systems
• Condition measures and properties of the central trajectory of a linear program
• Some perturbation theory for linear programming
• On the complexity of linear programming under finite precision arithmetic
• Connections between the total least squares and the correction of an infeasible system of linear inequalities
• Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems
• On the complexity of solving feasible systems of linear inequalities specified with approximate data
• Probabilistic analysis of the Grassmann condition number
• A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints
• On the block-structured distance to non-surjectivity of sublinear mappings
• Ill-posedness with respect to the solvability in linear optimization
• Extreme points of well-posed polytopes
• scientific article; zbMATH DE number 1008382 (Why is no real title available?)
• On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data
• The Condition Number of Riemannian Approximation Problems
• K-best feasible clusters - ranking optimal solutions from an infeasible LP
• Smoothed analysis of condition numbers and complexity implications for linear programming

This page was built for publication: Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs

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