- Equivalences among the chi measure, Hoffman constant, and Renegar's distance to ill-posedness Javier Pena(jfpandrew.cmu.edu) Juan Vera(j.c.veralizcanouvt.nl) Luis Zuluaga(luis.zuluagalehigh.edu) Abstract: We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a procedure to estimate $\chi(A)$ thereby opening an avenue to identify classes of linear programs solvable in polynomial time in the real model of computation. Keywords: condition measures, chi measure, Hoffman constant, distance to ill-posedness, signed matrices Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 3: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Technical Report, Carnegie Mellon University, May 2019. Download: [PDF]Entry Submitted: 05/15/2019Entry Accepted: 05/15/2019Entry Last Modified: 05/15/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.