Solving Linear Programs without Breaking Abstractions
Solving Linear Programs without Breaking Abstractions
复制标题
在不破坏抽象的情况下求解线性规划
DOI：
10.1145/2822890
复制
发表时间：
2015
影响因子：
2.5
通讯作者：
Anderson M
中科院分区：
文献类型：
--
作者：
Anderson M
我们表明，椭球方法求解线性规划可以实现的方式，尊重对称性的程序解决。也就是说，存在方法的算法实现，该算法实现不区分或选择程序中的变量或约束，除非它们通过可从程序定义的属性来区分。特别是，我们证明了线性规划的可解性可以表示在不动点逻辑计数（FPC），只要该计划是由一个分离的预言，本身是在FPC定义。我们用这个来表明，在一个图中的最大匹配的大小是可定义的FPC。这解决了Blass、Gurevich和Shelah [Blass et al. 1999]首先提出的一个开放性问题。在为最大匹配规划定义合适的分离预言机的过程中，我们给出了定义无向容量限制图的标准最大流和最小割的FPC公式。
We show that the ellipsoid method for solving linear programs can be implemented in a way that respects the symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the program. In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed by Blass, Gurevich and Shelah [Blass et al. 1999]. On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected capacitated graphs.
登录
查看更多内容
带计数的定点逻辑中的最大匹配和线性规划
DOI：
10.1109/lics.2013.23
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Anderson M
通讯作者：
Anderson M
利用空间膨胀运算来最小化凸函数
DOI：
--
发表时间：
1972
期刊：
影响因子：
--
作者：
N. Z. Shor
通讯作者：
N. Z. Shor
DOI：
--
发表时间：
2001
期刊：
Journal of Symbolic Logic (JSL)
影响因子：
--
作者：
A. Blass;Y. Gurevich;S. Shelah
通讯作者：
S. Shelah
无选择计算和对称性
DOI：
--
发表时间：
2010
期刊：
Fields of Logic and Computation
影响因子：
--
作者：
Benjamin Rossman
通讯作者：
Benjamin Rossman
影响因子：
0.5
作者：
Anderson M
通讯作者：
Anderson M