Feb, 2022

使用 ASP 和 Datalog 计算 H-Partitions

PDF
TL;DR本文研究了陈述图 H 的限制条件下，有限无向简单图 G 的 H - 划分问题。作者使用带分层否定的 Datalog 表达式描述了多项式时间算法，并在 Clingo 上进行了实验比较，结果表明比起等价的 Datalog 程序，直接猜测和检查程序在 Clingo 上运行更快。
h-partitionmodel graphdatalogpolynomial timeclingo
发现论文，激发创造
  • 面向答案集编程中猜测和检查程序的自动集成：元解释器和应用

    本文提出将无环扩展析取逻辑程序转化为分层正向扩展析取逻辑程序的方法并将研究应用于 ASP 中这一强大的工具，扩展了现有策略在编程范式中的应用，进一步提高了处理 NP 问题的方法。

    Jan, 2005

  • 通过图论对私有可学习性的统一刻画

    本文提供了一个统一的框架来表征纯和近似差分隐私 (DP) 可学习性。我们使用图论语言来定义 $mathcal {H}$ 的矛盾图 $G$，并发现 $G$ 的组合结构与在 DP 下学习 $mathcal {H}$ 有着深刻的联系。

    Apr, 2023

  • 基于启发式分解的答案集计算优化

    该研究提出了一种新的优化方法，基于树分解技术和启发式算法，可以将一个输入的逻辑程序转化为一个等价的程序以提高 ASP 系统的求解效率，并在实验中验证了其有效性。

    Dec, 2018

  • 在高维结构假设空间上的因果发现与因果图分区

    我们定义了一种新颖的因果图分区方法，利用超结构的概念对搜索空间进行划分，证明了使用因果图分区进行学习总是得到真实因果图的马尔可夫等价类，我们的算法在生物调节网络推断和其他高维结构假设空间中实现了可比较的准确性和更快的解决时间。

    Jun, 2024

  • d - 正则图上双自旋模型计数的计算困难性

    该研究探讨了对于在 d - 正则图上，存在非唯一性的两个自旋系统（包括独立集模型和反铁磁伊辛模型），在逼近其配分函数或者用该模型逼近抽样是 NP 难的。同时，该研究提出了一种新的方法，用二分图本地树状图结构来描述两自旋系统，并标志着通过随机化降低最大割问题的计算复杂性的新里程碑。

    Mar, 2012

  • 非连续逻辑程序的回归正常

    研究了如何利用命题可满足性 (SAT) 解决比 NP 或 co-NP 更困难的问题，特别是对命题析取答案集编程中的基本推理问题进行探讨，介绍了利用新的 Parameterized Complexity 技术从 Brave 和 Skeptical Reasoning 转换到 SAT 的方法。

    Jan, 2013

  • 不均匀超图聚类与应用

    提出了一种新的超图聚类技术，称为不均匀超图划分，其将不同的代价分配给不同的超图切割，证明了如果不均匀代价满足次模性约束，则不均匀划分产生了最优解的二次近似，并证明了在许多应用中可以获得显着的性能改进。

    Sep, 2017

  • 快速平衡划分尽管在网格和树上也很困难

    本文探讨了 k-Balanced Partitioning 问题的两类近似算法：快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明，这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架，以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。

    Nov, 2011

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

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

    Feb, 2024

  • 使用极限 Datalog 程序的声明性数据分析基础

    研究了正 Datalog 上添加整数算术函数的扩展语言 Datalog_Z，并提出了两个限制子语言 limit Datalog_Z 和 stable Datalog_Z 以解决其不可判定性，并证明了相应的 NP 完全性和 ExpTime 完全性，最终表明稳定的 Datalog_Z 能够表达许多有用的数据分析任务，为先进信息系统的发展提供了一个坚实的基础。

    May, 2017