A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
复制标题
一种线性规划的缩放不变算法，其运行时间仅取决于约束矩阵
DOI：
10.1145/3357713.3384326
复制
发表时间：
2019
影响因子：
2.7
通讯作者：
L. V'egh
中科院分区：
文献类型：
--
作者：
D. Dadush;Sophie Huiberts;Bento Natura;L. V'egh
Following the breakthrough work of Tardos (Oper Res 34:250–256, 1986) in the bit-complexity model, Vavasis and Ye (Math Program 74(1):79–120, 1996) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) $$\max \, c^\top x,\, Ax = b,\, x \ge 0,\, A \in \mathbb {R}^{m \times n}$$ max c ⊤ x , A x = b , x ≥ 0 , A ∈ R m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that $$O(n^{3.5} \log (\bar{\chi }_A+n))$$ O ( n 3.5 log ( χ ¯ A + n ) ) iterations suffice to solve (LP) exactly, where $$\bar{\chi }_A$$ χ ¯ A is a condition measure controlling the size of solutions to linear systems related to A . Monteiro and Tsuchiya (SIAM J Optim 13(4):1054–1079, 2003), noting that the central path is invariant under rescalings of the columns of A and c , asked whether there exists an LP algorithm depending instead on the measure $$\bar{\chi }^*_A$$ χ ¯ A ∗ , defined as the minimum $$\bar{\chi }_{AD}$$ χ ¯ AD value achievable by a column rescaling AD of A , and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an $$O(m^2 n^2 + n^3)$$ O ( m 2 n 2 + n 3 ) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying $$\bar{\chi }_{AD} \le n(\bar{\chi }_A^*)^3$$ χ ¯ AD ≤ n ( χ ¯ A ∗ ) 3 . This algorithm also allows us to approximate the value of $$\bar{\chi }_A$$ χ ¯ A up to a factor $$n (\bar{\chi }_A^*)^2$$ n ( χ ¯ A ∗ ) 2 . This result is in surprising contrast to that of Tunçel (Math Program 86(1):219–223, 1999), who showed NP-hardness for approximating $$\bar{\chi }_A$$ χ ¯ A to within $$2^{\textrm{poly}(\textrm{rank}(A))}$$ 2 poly ( rank ( A ) ) . The key insight for our algorithm is to work with ratios $$g_i/g_j$$ g i / g j of circuits of A -i.e., minimal linear dependencies $$Ag=0$$ A g = 0 -which allow us to approximate the value of $$\bar{\chi }_A^*$$ χ ¯ A ∗ by a maximum geometric mean cycle computation in what we call the ‘circuit ratio digraph’ of A . While this resolves Monteiro and Tsuchiya’s question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved $$O(n^{2.5} \log (n)\log (\bar{\chi }^*_A+n))$$ O ( n 2.5 log ( n ) log ( χ ¯ A ∗ + n ) ) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $$n/\log n$$ n / log n improvement on the iteration complexity bound of the original Vavasis–Ye algorithm.
Following the breakthrough work of Tardos (Oper Res 34:250–256, 1986) in the bit-complexity model, Vavasis and Ye (Math Program 74(1):79–120, 1996) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) $$\max \, c^\top x,\, Ax = b,\, x \ge 0,\, A \in \mathbb {R}^{m \times n}$$ max c ⊤ x , A x = b , x ≥ 0 , A ∈ R m × n , Vavasis and Ye developed a primal-dual interior point method using a ‘layered least squares’ (LLS) step, and showed that $$O(n^{3.5} \log (\bar{\chi }_A+n))$$ O ( n 3.5 log ( χ ¯ A + n ) ) iterations suffice to solve (LP) exactly, where $$\bar{\chi }_A$$ χ ¯ A is a condition measure controlling the size of solutions to linear systems related to A . Monteiro and Tsuchiya (SIAM J Optim 13(4):1054–1079, 2003), noting that the central path is invariant under rescalings of the columns of A and c , asked whether there exists an LP algorithm depending instead on the measure $$\bar{\chi }^*_A$$ χ ¯ A ∗ , defined as the minimum $$\bar{\chi }_{AD}$$ χ ¯ AD value achievable by a column rescaling AD of A , and gave strong evidence that this should be the case. We resolve this open question affirmatively. Our first main contribution is an $$O(m^2 n^2 + n^3)$$ O ( m 2 n 2 + n 3 ) time algorithm which works on the linear matroid of A to compute a nearly optimal diagonal rescaling D satisfying $$\bar{\chi }_{AD} \le n(\bar{\chi }_A^*)^3$$ χ ¯ AD ≤ n ( χ ¯ A ∗ ) 3 . This algorithm also allows us to approximate the value of $$\bar{\chi }_A$$ χ ¯ A up to a factor $$n (\bar{\chi }_A^*)^2$$ n ( χ ¯ A ∗ ) 2 . This result is in surprising contrast to that of Tunçel (Math Program 86(1):219–223, 1999), who showed NP-hardness for approximating $$\bar{\chi }_A$$ χ ¯ A to within $$2^{\textrm{poly}(\textrm{rank}(A))}$$ 2 poly ( rank ( A ) ) . The key insight for our algorithm is to work with ratios $$g_i/g_j$$ g i / g j of circuits of A —i.e., minimal linear dependencies $$Ag=0$$ A g = 0 —which allow us to approximate the value of $$\bar{\chi }_A^*$$ χ ¯ A ∗ by a maximum geometric mean cycle computation in what we call the ‘circuit ratio digraph’ of A . While this resolves Monteiro and Tsuchiya’s question by appropriate preprocessing, it falls short of providing either a truly scaling invariant algorithm or an improvement upon the base LLS analysis. In this vein, as our second main contribution we develop a scaling invariant LLS algorithm, which uses and dynamically maintains improving estimates of the circuit ratio digraph, together with a refined potential function based analysis for LLS algorithms in general. With this analysis, we derive an improved $$O(n^{2.5} \log (n)\log (\bar{\chi }^*_A+n))$$ O ( n 2.5 log ( n ) log ( χ ¯ A ∗ + n ) ) iteration bound for optimally solving (LP) using our algorithm. The same argument also yields a factor $$n/\log n$$ n / log n improvement on the iteration complexity bound of the original Vavasis–Ye algorithm.
中等密集图上近线性时间的二分匹配
DOI：
10.1109/focs46700.2020.00090
发表时间：
2020
期刊：
2020
影响因子：
--
作者：
van den Brand, Jan;Lee, Yin-Tat;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
通讯作者：
Wang, Di
影响因子：
3.1
作者：
De Loera, Jesús A.;Kafer, Sean;Sanità, Laura
通讯作者：
Sanità, Laura
一种更简单、更快速的广义流最大化的强多项式算法
DOI：
10.1145/3055399.3055439
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Olver N
通讯作者：
Olver N