Jun, 2013

参数化枚举范例

PDF
TL;DR本文旨在从参数化复杂度的角度，探究枚举计算复杂度和算法问题，首先定义了不同的枚举概念，然后运用不同算法，例如核函数和自减技术，从而得到参数有效的枚举算法，并且通过核函数的概念，对固定参数极易枚举的问题进行了表述。
computational complexityalgorithmicsenumerationparameterized complexitykernelization
发现论文，激发创造
  • 电路定义的枚举类

    本文通过将布尔电路定义为枚举器引入低复杂度类，定位了多个枚举问题并将其归入该类，从而获得了一个能够区分不同问题复杂度的框架，为解决一直以来难以进行比较的延迟 - P 问题带来新的思路。

    May, 2022

  • 解的多样性：从固定参数可计算性理论角度的探索

    本研究在固定参数可解性理论的视角下，对于充分多样的好解的集合进行了系统化研究，并提出了一种基于树分解的动态规划算法框架，将已知的求解算法转化为充分多样的好解动态规划算法，其中多样性参数具有多项式依赖性。

    Mar, 2019

  • 逻辑程序语义的固定参数复杂度

    该研究以逻辑程序模型为背景，讨论了固定参数复杂度、参数化决策问题以及稳定模型等方面的研究，发现设置模型边界以解决问题的算法并不可行，提出了对于多项式时间算法的更好期望。

    Jul, 2001

  • 计算社会选择的参数化算法：九个研究挑战

    这篇论文提出了与计算社会选择和参数化算法相关的九个挑战。

    Jul, 2014

  • Kemeny 排名聚合的多样性：参数化方法

    研究表明，通过将方案多样性与参数化复杂性理论相结合，可以使用基于算法的框架解决实际相关问题，例如 Kemeny Rank 聚合问题。

    May, 2021

  • 细粒度搜索空间分类用于求解子集问题的困难枚举变体

    本文提出了一个简单，强大和灵活的机器学习框架，用于减少计算困难的集合问题的枚举变量搜索空间，并通过输入分布产生的信息提示来增强现有的最先进的求解器。我们将我们的框架实例化为图中列出所有最大团的问题，这是网络分析，数据挖掘和计算生物学中的中心问题。我们证明了我们的方法在具有数百万个顶点和边的真实世界网络上的实用性，不仅保留了所有最优解，而且还积极剪枝输入实例大小，导致比最先进的算法快几倍。最后，我们探讨了我们提出的框架的可扩展性和鲁棒性的限制，表明监督学习在实践中应用于 NP-hard 问题是可行的。

    Feb, 2019

  • 枚举压缩与收益

    研究枚举的可压缩性及其在可计算可枚举集合相对 Kolmogorov 复杂度方面的作用，并针对压缩的强和弱形式研究其增益，证明了任何可计算可枚举集合都具有强压缩和无增益弱压缩，并研究一种位置游戏以深入理解强无增益压缩。

    Apr, 2023

  • 互动决策中不同支持向量的枚举

    本文提出了一种针对支持向量机（SVM）的 K-best 模型枚举算法，该算法在支持向量的格子结构分析的基础上，以双重 SVM 问题的目标函数值降序排列的方式，枚举了具有不同支持向量的数据集 S 的 K-best 模型。

    Jun, 2019

  • 有限规划的完整参数化复杂度分析

    该论文研究了参数化复杂性下命题性规划问题的分类，重点关注了解决方案计划的长度参数和常见的句法限制，包括 PUBS 限制和条件 / 效果数量限制，并确定哪些问题适用于多项式内核，哪些不适用。

    Oct, 2013

  • 自动算法选择：调研和视角

    该文概述了自动算法选择的研究，涵盖离散问题和连续问题的应用，并讨论算法配置、调度或组合选择等相关方法。此外，文章还提供了离散问题和连续问题的问题实例特征概述，并对未来的工作进行了展望，讨论了许多开放性的研究挑战。

    Nov, 2018