Jul, 2009

达到紧密下界的最大 r-SAT 问题求解

PDF
TL;DR提出了一个精确算法，决定在时间复杂度 O (m)+2^{O (k^2)} 内，对于每个固定的 r≥2，是否存在一个满足至少 ((2^r-1) m+k)/2^r 个子句的布尔表达式，从而解决 Mahajan 等人未解决的开放问题。该算法基于一个在多项式时间内缩小问题规模的数据约减过程，并介绍了一种新的从参数化问题到另一个参数化问题的生物核化方法，并将其应用于证明所提出的问题具有多项式大小的内核。同时，将定参数可跟踪性和多项式大小内核的结果推广到更广泛的布尔约束满足问题。
max-r-satfixed-parameter tractabilitypolynomial-size kerneldata reduction procedureboolean constraint satisfaction problems
发现论文，激发创造
  • 低次多项式随机 $k$- 可满足性问题的算法相变

    研究了在 $k$-SAT 问题中寻找满足分配的算法任务，证明了低次数多项式算法类无法在特定子密度下解决该问题，这是关于任何算法类在与 Fix 相等水平难度下的首个困难结果。

    Jun, 2021

  • 用低秩半定规划解决 MAX2SAT 问题

    本文提出了一种将搜索方法与半定规划方法相结合的算法，其用于解决 MAX2SAT 问题。文中称，使用这种方法能够显著提高问题的解决速度，并在一些问题上取得了 order of magnitude 级别的速度提升。

    Dec, 2018

  • 随机可满足性问题中的种植解的复杂性

    本文提出和研究了一种插入 k-SAT 模型，描述了一个插入分配 σ 和一个具有 k 个文字的子句分布的实例，对于分布复杂性的倒数关联了查询算法的统计下界。该证明引入了一种新的分析统计查询算法的通用技术，并指出了所有种植任务空间中的几何剪枝现象。

    Nov, 2013

  • 关于大 k 可满足性猜想的证明

    我们利用统计物理学中的一步副本对称性预测，为所有的 k≥k_0，建立了随机 k-SAT 的可满足性阈值，给出满足阈值和不满足阈值的限制密度的显式计算公式，并用一种新的分析方法对随机图进行矩计算，将一个高维的优化问题映射到了一个更易处理的分析树递归问题，证明了我们的阈值计算方法适用于 1-RSB 普适性类中的各种随机约束满足问题。

    Nov, 2014

  • 基于拟阵约束的 k 次次模最大化的快速算法

    应用阈值减小算法最大化满足 matroid 约束的 k - 次模函数，提出逼近算法来最大化满足单调和非单调 k - 次模函数，并提供了关于时间复杂度的结果，同时还介绍了针对总大小约束的快速算法。

    Jul, 2023

  • 挑战 SAT 求解中分辨率限制

    本文提出了一种新的问题转化方法，将 CNF 公式的决策问题转化为 Horn 公式的最大可满足性问题，并证明了在鸽笼公式的情况下 MaxSAT resolution steps 的数量存在多项式绑定。

    May, 2017

  • 将 SAT 问题化简为 Max2XOR 问题

    本文提出了将 SAT 子句翻译成至多两个变量等于零或一的 XOR 子句的 Max2XOR 约束的装置，并提出了 Max2XOR 问题的新的解析规则，以提高求解效率。

    Apr, 2022

  • UpMax：用戶分區的 MaxSAT

    本文提出了一种新的框架 UpMax，将分割过程与 MaxSAT 解决算法分离，使用户能够根据问题来提出分割方案，证明分割对于基于不可满足性的 MaxSAT 算法的性能有很大的影响。

    May, 2023

  • 学习带单样本硬约束的模型

    使用单个样本估计具有硬约束的马尔可夫随机场的参数，算法基于伪似然估计器，对于 $k$-SAT 和 proper coloring 模型以及一般的 $H$-coloring 模型，不仅获得了正面结果，还获得了负面结果。

    Nov, 2023

  • 舍入平方和松弛问题

    通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。

    Dec, 2013