Metraipolis › archive › dc_672763333f14
On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation — arXiv:2608.12550
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.12550
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T04:46:27.202Z
- SHA-256 of the archived text
2c06fa008e6d440b2a3582bf06f7b130905a24b39cdf02126613a05c84baa205- Stable URL of this page
https://metraipolis.com/documento/dc_672763333f14
How to cite
On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation — arXiv:2608.12550 — arXiv (en), https://arxiv.org/abs/2608.12550 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_672763333f14 (Metraipolis archive dc_672763333f14, sha256 2c06fa008e6d440b2a3582bf06f7b130905a24b39cdf02126613a05c84baa205)
BibTeX
@misc{dc672763333f14,
title = {On the Exponential Circuit Imbalance of the Ben-Tal Nemirovski Approximation — arXiv:2608.12550},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.12550},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_672763333f14; sha256 2c06fa008e6d440b2a3582bf06f7b130905a24b39cdf02126613a05c84baa205},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12550. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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$. Monteiro-Tsuchiya (2003) defined the optimal condition number $\bar{\chi}_A^*$ as the maximum $\bar{\chi}_{AD}$ achievable over all positive diagonal column rescalings $D$. Dadush et al.\ (2024) introduced the optimal circuit imbalance measure $\kappa_W^*$, which serves as a lower bound for $\bar{\chi}^*_A$. Instances with artificially large optimal circuit imbalance measures $\kappa_W^*$ can be easily constructed; however, finding naturally occurring examples where this optimal scaling-invariant measure grows exponentially is of independent interest. In this paper, we show that the Ben-Tal Nemirovski (BN) linear programming approximation of the unit disk provides such an example. By explicitly constructing circuits in the kernel of the BN formulation, we prove that the optimal circuit imbalance measure $\kappa_W^*$ grows exponentially in the number of approximation steps. Since $\kappa_W^*$ lower bounds $\bar{\chi}_A^*$, our result demonstrates that the BN approximation yields an exponentially ill-conditioned family of constraint matrices.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-14 in math.OC).
Categorie arXiv: Computational Complexity (cs.CC) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.12550 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T04:27:11.031Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).