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

DOI10.1137/S105262349223352XzbMath0856.90077MaRDI QIDQ4895608

Jorge R. Vera

Publication date: 3 February 1997

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

zbMATH Keywords

existence of solutionsconditioningapproximate data

Mathematics Subject Classification ID

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

Related Items (14)

K-best feasible clusters - ranking optimal solutions from an infeasible LP ⋮ Some perturbation theory for linear programming ⋮ Extreme points of well-posed polytopes ⋮ On the complexity of solving feasible systems of linear inequalities specified with approximate data ⋮ On the complexity of linear programming under finite precision arithmetic ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints ⋮ Connections between the total least squares and the correction of an infeasible system of linear inequalities ⋮ On the block-structured distance to non-surjectivity of sublinear mappings ⋮ Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems ⋮ On optimal zero-preserving corrections for inconsistent linear systems ⋮ Condition measures and properties of the central trajectory of a linear program ⋮ The Condition Number of Riemannian Approximation Problems ⋮ Probabilistic analysis of the Grassmann condition number

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