On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System

DOI10.1287/moor.28.4.625.20509zbMath1082.90152OpenAlexW2099544989MaRDI QIDQ5704144

Robert M. Freund, Jorge R. Vera

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/24a933d15afd63678b772f1c40992b784b4d371f

zbMATH Keywords

semidefinite programmingerror analysisconditioninginterior-point methodscomplexity theoryComplexity of linear programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31)

Related Items (8)

Extreme points of well-posed polytopes ⋮ On two measures of problem instance complexity and their correlation with the performance of SeDuMi on second-order cone problems ⋮ Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information ⋮ Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems ⋮ Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization ⋮ On the block-structured distance to non-surjectivity of sublinear mappings ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ Complexity indices for the multidimensional knapsack problem

This page was built for publication: On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System