A new condition number for linear programming
From MaRDI portal
Publication:5955567
DOI10.1007/s101070100237zbMath1072.90564OpenAlexW75893293MaRDI QIDQ5955567
Publication date: 2001
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s101070100237
Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)
Related Items (24)
Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ A characterization of the distance to infeasibility under block-structured perturbations ⋮ A condition-based algorithm for solving polyhedral feasibility problems ⋮ Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization ⋮ Some preconditioners for systems of linear inequalities ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ A simple polynomial-time rescaling algorithm for solving linear programs ⋮ Stability under perturbations of some condition numbers in optimization ⋮ Coverage processes on spheres and condition numbers for linear programming ⋮ On strata of degenerate polyhedral cones. II: Relations between condition measures ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF ⋮ Solving linear programs with finite precision. II: Algorithms ⋮ On the von Neumann and Frank--Wolfe Algorithms with Away Steps ⋮ The condition number of a function relative to a set ⋮ A Data-Independent Distance to Infeasibility for Linear Conic Systems ⋮ A hybrid branch-and-bound approach for exact rational mixed-integer programming ⋮ Towards a deeper geometric, analytic and algorithmic understanding of margins ⋮ Randomized Gradient Boosting Machine ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ Conditioning of random conic systems under a general family of input distributions ⋮ The Condition Number of Riemannian Approximation Problems ⋮ Probabilistic analysis of the Grassmann condition number ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
This page was built for publication: A new condition number for linear programming
