{"id":"arxiv/2608.12550","url":"https://arxiv.org/abs/2608.12550","tags":["cs.CC","math.OC"],"score":0,"title":"On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation","domain":"cs.CC","source":"arxiv","authors":["Jonah Bondar","Stephen Vavasis"],"reviews":0,"subject":"cs.CC","summary":"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χ_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χ_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number $\\barχ_A^*$ as the maximum $\\barχ_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\\ (2024) introduced the optimal circuit imbalance measure $κ_W^*$, which serves…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}