On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data

DOI10.1137/S1052623494268467MaRDI QIDQ4702320zbMATH OpenOpenAlexFDO

Authors Sharon Filipowski

Publication date 24 November 1999

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

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

zbMATH Keywords

approximate dataapproximate solutionscomplexity of linear programmingcondition measuresknowledge

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of solving feasible systems of linear inequalities specified with approximate data
• On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data
• scientific article; zbMATH DE number 1099078
• Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs

Cited in

(11)

• Approximate linear algebra is intractable
• On the complexity of solving feasible systems of linear inequalities specified with approximate data
• Probabilistic analysis of the Grassmann condition number
• How partial knowledge helps to solve linear programs
• Improved complexity results on solving real-number linear feasibility problems
• Extreme points of well-posed polytopes
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• scientific article; zbMATH DE number 1099078 (Why is no real title available?)
• On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data
• Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
• Data mapping of linear programming on fixed-size hypercubes

This page was built for publication: On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data

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