On circuit diameter bounds via circuit imbalances

• 成果类型: Article; Early Access
• 署名作者: Dadush, Daniel; Koh, Zhuan Khye; Natura, Bento; Vegh, Laszlo A.
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02107-x
• 发表日期: 2024
• 关键词: cycle-canceling algorithm; minimum; augmentation

摘要

We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIAM J. Discrete Math. 29(1), 113-121 (2015)) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system {x is an element of Rn:Ax=b,0 <= x <= u}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{x\in \mathbb {R}<^>n:\, Ax=b,\, \mathbb {0}\le x\le u\}$$\end{document} for A is an element of Rmxn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A\in \mathbb {R}<^>{m\times n}$$\end{document} is bounded by O(mmin{m,n-m}log(m+kappa A)+nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(m\min \{m, n - m\}\log (m+\kappa _A)+n\log n)$$\end{document}, where kappa A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa _A$$\end{document} is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound if e.g., all entries of A have polynomially bounded encoding length in n. Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an LP in O(mn2log(n+kappa A))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(mn<^>2\log (n+\kappa _A))$$\end{document} augmentation steps.