Nov, 2020

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

PDF
TL;DR本文提出了一种基于内点法和树分解的线性规划问题求解算法，可以在近似相对误差为 ε 的情况下，在时间复杂度 Θ(n ⋅ tw² ⋅ log (1/ε)) 内求解给定的线性规划问题，其中 tw 是输入图的树宽，并且是第一个时间复杂度与子问题 Ax=b 的最快时间复杂度相匹配的算法。
treewidthlinear programmingtree decompositioninterior-point methodsrelative accuracy
发现论文，激发创造
  • 基于树宽求解问题的高级工具和方法 - 扩展摘要

    本文主要研究了基于逻辑的问题及基于 treewidth 的方法和工具，并提出了一种新类型的问题降解方法，其中问题为有界 treewidth 的量化布尔公式（QBF）。结果表明，treewidth 是设计现代求解器时应考虑的一项重要的测量标准。

    Aug, 2022

  • 阈值树宽和超树宽

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

    Oct, 2022

  • 利用树宽及其限制条件解决投影模型计数问题

    本文介绍了一种新算法来解决投影模型计数（PMC）问题，该算法利用输入实例的原始图的小树宽，并在同时考虑了指标化的树宽有理论下限的情况下，提供固定参数可解，通过使用嵌套动态规划，并在数据库技术的帮助下，可以解决树宽上限超过 200 的实例的 PMC 问题和热门的 PMC 特殊情况＃Sat。

    May, 2023

  • 利用低树宽计算所有对最短路径

    本论文提出了两种新的算法，用于计算带有实数边权（可能为负数）的有向图的全源最短路径。这两种算法运行时间复杂度为 O (n^2w_d)，可用于空间和时间推理，比 Floyd-Warshall 算法和 Johnson 算法更快，并且具有规划和调度社区的相关性。

    Jan, 2014

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

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

    Oct, 2016

  • 利用数据库管理系统和树宽进行计数

    本文提出了一种基于数据库管理系统的通用框架来解决具有小分解树宽度的问数问题，利用动态规划在分解树上进行计算，并将 DP 算法实现到了一个 DBMS (PostgreSQL) 中。这是我们的实验室采用 DBMS 进行处理 TDs 算法的第一次尝试，我们的方法具有处理大型数据表，多核并行计算，以及中止计算等显而易见的优势。

    Jan, 2020

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

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

    May, 2022

  • 一种完整的任意时刻用于树宽算法

    本文提出了一种基于分支界限算法的快速计算无向图树宽的算法 QuickBB，包括理论基础与算法实现，可以应用于任何无向图，并对该算法的实验结果进行了比较和分析。

    Jul, 2012

  • QBF 作为 Courcelle 定理的替代

    本文采用量化布尔公式减少作为一种新的方法来展示固定参数线性算法，研究人工智能领域的几个已知问题，其中大部分问题已经通过使用 Courcelle 定理或动态规划证明了其固定参数线性，但作者认为采用 量化布尔公式 减少这种方法具有明显的优势。

    May, 2018

  • 在当前矩阵乘法时间内解决线性规划问题

    本文介绍了一种解决线性规划问题的算法，旨在在对矩阵乘法进行研究后，以次二次时间复杂度解决规模为 n 的问题，同时提出了新的概念，如随机中心路径法和投影矩阵等。

    Oct, 2018