在半环上计算基于广义模式的能量的分配函数
研究定值约束满足问题,利用基本线性规划松弛和对称分数多项式的精确代数刻画,实现了多个类的问题的可处理性,包括在任意格上子模的问题,任意有限域上的 k - 子模问题,任意树上具有弱(hence 强)树子模的问题。
Nov, 2013
该文提出了一种基于小块标记枚举的大图通用最小化方法,可用于复杂高阶能量的优化。该方法在曲率正则化等难解问题上表现优越,并通过一种新颖的积分几何方法直接评估小块的曲率。
Mar, 2013
本文研究约束满足问题 (CSP) 中变量或值的消除对于减小搜索空间的影响和作用,提出了四种变量消除规则和三种值消除规则,这些规则都是在禁止存在特定的不可约存在模式的前提下,在弧一致 CSP 实例中进行定义和应用。其中三种变量消除规则是新的,而另一种已经被认知的规则是 Broken Triangle Property。这三种值消除规则都可以看做是同邻居替换法的一种更为广泛的推广。
Feb, 2015
本文介绍了一种基于判别学习的方法来寻找高阶先验,该方法采用了结构化 SVM 和用于求解子模流问题的延伸割算法,说明了如何更好地利用子模函数的表达能力,实现更好的交互式分割技术。
Sep, 2013
本文介绍了两种新型随机逼近算法 —— 协作随机逼近算法(CSA)和协作随机参数逼近算法(CSPA),分别用于处理决策变量约束和问题参数约束的期望函数最小化问题,证明了它们实现了最优收敛率以及不需要使用对偶变量迭代。
Apr, 2016
本文研究了扩展时序约束问题的复杂性,并针对一组量词自由的 “小于等于(leq)” 公式所形成的 Poset-SAT 问题进行了讨论。其问题是对于 $x_1$,$x_2$,…,$x_n$ 成为偏序集时是否存在满足给定公式的赋值。最后,作者使用模型理论概念和通用代数技术研究了这些问题的约束满足问题,并提出了独立于通用代数和模型理论的分裂定理。
Feb, 2016
通过转换一个分布映射算法为一个近似解,我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法,并应用于 3 个已知问题的改进,分别是:低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。
Dec, 2013
本文介绍了一种基于指数域的分布的凸组合的对数划分函数的新的上界类型,适用于任何无向图模型,特别是树形结构分布的凸组合。该方法有唯一全局最小值,可以用于原模型的边际估计。此方法与更高的 treewidth 的结构相关联,从而与更高级的近似方法相关。
Dec, 2012