On the exponential circuit imbalance of the Ben-Tal Nemirovski approximation
Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye’s (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. The optimal condition measure $\bar{\chi}_A^*$ is defined … Read more