研究定值约束满足问题,利用基本线性规划松弛和对称分数多项式的精确代数刻画,实现了多个类的问题的可处理性,包括在任意格上子模的问题,任意有限域上的 k - 子模问题,任意树上具有弱(hence 强)树子模的问题。
Nov, 2013
通过证明各种规约保持 Lasserre SDP 层次的精确可解性,我们展示了支持破坏有限宽度条件的一般值约束语言不能被静态程序快速求解。
Dec, 2016
该论文研究了一种特殊情况的约束满足问题,其中变量完全有序并对不违反顺序的变量元组施加软约束;为不同类型的约束语言和权重提供了计算模式的解决方案,以获得约束最小化的解决方案。
May, 2023
证明了对于约束满足问题的近似版本,线性规划松弛的规模存在超多项式下界,并且对于这些问题,多项式大小的线性规划方案与一定轮数的 Sherali-Adams 层次中产生的方案具有相同的能力;具体来说,最大割的多项式大小线性规划的可积性差可能性上界为 1/2,而最大三种满足问题的多项式大小线性规划则可能性上界为 7/8。
Sep, 2013
该论文研究了基于约束满足问题的自然组合问题如何表达的问题,分类了可在多项式时间内解决和 NP 完全的子类,并从约束语言的角度提出了一个算法来解决约束满足问题。
Apr, 2017
本文研究了一种统一的框架方法用于解决一类混合整数优化问题,通过对其逻辑约束进行非线性方式的表达,结合规则化条件及基于混合精度算法,形成了凸二进制优化问题,并利用一种综合的数字策略方法解决问题。
Jul, 2019
本研究提出了一种新颖的加权技术算法,以解决最大化单调子模函数和线性函数总值的问题, 该问题在一般可解的多面体约束条件下, 相对于 Sviridenko 等人 2017 年提出的算法推断步骤更为简单,但其保持了相同的近似保证。
Oct, 2018
本文介绍了一个算法,用于找到具有给定列表中的类中的离散类的强后门,这些类由 CSP 实例中的连通分量确定,并表明满足特定条件时,可以通过这种方式超越 CSP 的易处理性限制。
Jul, 2015
研究了约束满足问题中基本关系具有小拼接性质的 CSP,提出了一种求解这类问题的算法,时间复杂度为 f (w)・n^{O (1)},并且不仅限于二元约束。
Jul, 2021
本文研究约束满足问题 (CSP) 中变量或值的消除对于减小搜索空间的影响和作用,提出了四种变量消除规则和三种值消除规则,这些规则都是在禁止存在特定的不可约存在模式的前提下,在弧一致 CSP 实例中进行定义和应用。其中三种变量消除规则是新的,而另一种已经被认知的规则是 Broken Triangle Property。这三种值消除规则都可以看做是同邻居替换法的一种更为广泛的推广。
Feb, 2015