Jul, 2022

二元 CSP 及其半环泛化的组件双宽度参数

PDF
TL;DR本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性，探讨了基于半环的代数方法，提出了组件双宽属性的 generalization。研究表明，在受限制的条件下，该方法在多种问题中取得了优秀算法复杂度上界。
constraint satisfaction problemssemiringstwin-width parameteralgorithmic approachcomplexity upper bounds
发现论文，激发创造
  • 阈值树宽和超树宽

    介绍了树宽和超树宽的概念，并通过计算阈值树宽和超树宽，提出了一种固定参数算法，可在多项式时间内解决 CSP 问题。

    Oct, 2022

  • 利用拼块特性解决无限域 CSP 问题

    研究了约束满足问题中基本关系具有小拼接性质的 CSP，提出了一种求解这类问题的算法，时间复杂度为 f (w)・n^{O (1)}，并且不仅限于二元约束。

    Jul, 2021

  • 结合树宽和后门求解 CSP 问题

    本研究论文表明，当以任何可转化为有限约束语言的可解 CSP 问题作为背景门限时，CSP 是固定参数可解的，这将结合了两个解决 CSP 可解性问题的突出方法：(i) 通过变量和约束之间交互的结构限制和 (ii) 通过内部约束所使用的关系的语言限制。除了定义背景门限的概念并展示如何利用小的背景门限来高效求解 CSP 之外，本文主要技术贡献是提出了一种寻找小背景门限的固定参数算法。

    Oct, 2016

  • 从基于宽度的模型检查到基于宽度的自动定理证明

    该研究提出了一种通用框架，将基于宽度的模型检查算法转换为用于测试具有有限宽度图类的图论猜想的算法，并显示了在树宽度为 $k$ 的所有图上验证图论猜想的算法，时间为 $ k^{O (1)}$ 双指数级。

    May, 2022

  • 精准计算超图宽度测量

    该研究提出了一种通用的指数级算法来计算超图宽度之一的广义超树宽和分数超树宽，并建立了它们与树分解的联系，从而获得了快速准确算法。

    Jun, 2011

  • 小树幅线性规划的近线性时间算法：健壮中心路径的多尺度表示

    本文提出了一种基于内点法和树分解的线性规划问题求解算法，可以在近似相对误差为 ε 的情况下，在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题，其中 tw 是输入图的树宽，并且是第一个时间复杂度与子问题 Ax=b 的最快时间复杂度相匹配的算法。

    Nov, 2020

  • 关于 Answer-Set 编程的 Clique-Width 与有向宽度测量

    本文研究了绝对性集合编程中的困难问题，并提出了一种新的动态规划算法来解决一个图形参数问题，即带符号的团宽度（signed clique-width）

    Jun, 2016

  • 二元量化约束满足问题的混合可计算类

    本文研究二元量化约束满足问题的混合可处理性，利用破坏三角形性质识别了一类基本的可处理问题，通过引入破坏角度约束，打破了变量排序的限制，进一步识别出一些新的可处理问题，并最终确定了更广泛的可处理类型，即 QCSP 的 min-of-max 可扩展类。

    Apr, 2011

  • 在半环上计算基于广义模式的能量的分配函数

    该论文研究了一种特殊情况的约束满足问题，其中变量完全有序并对不违反顺序的变量元组施加软约束；为不同类型的约束语言和权重提供了计算模式的解决方案，以获得约束最小化的解决方案。

    May, 2023

  • 关于回答集编程的结构难度的延伸版本：结构能否有效地限制析取的能力？

    Answer Set Programming (ASP) 是一个以知识表示为重点的问题建模和求解框架，在工业应用方面有着快速增长。这篇论文通过对结构参数的分类研究了 disjunctive ASP 的复杂性，提供了多个重要参数的双指数下界，并指出除了 vertex cover size 之外的选项是有限的。

    Feb, 2024