Oct, 2020

最大独立集合的最佳低阶硬度

PDF
TL;DR研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。
发现论文，激发创造
  • 随机图中的独立集

    本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。

    Jul, 2010

  • 最大独立集的精确算法

    本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

    Dec, 2013

  • H - 自由图中最大权独立集问题的拟多项式时间逼近方案

    本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

    Jul, 2019

  • 稀疏随机图上本地算法的限制

    本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。

    Apr, 2013

  • 最大化固定大小独立集的数量

    研究独立集的数量及其最大化问题，通过证明假设得出其在最小度至少为 δ 的完全二分图中实现最大化。

    Nov, 2013

  • 利用独立集预言机进行边缘估计

    本研究探讨了使用独立集合查询进行图边估计的问题，并提出了两种算法来估计 n 个顶点的图中边的数量。

    Nov, 2017

  • 最大独立集问题的自适应重复交集约简局部搜索

    本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。

    Aug, 2022

  • 大规模寻找近似最优独立集

    本文提出一种应用进化算法和核技术求解大规模稀疏网络独立集问题的高效算法，并通过移除可能出现在大独立集中的顶点来加速计算，并在此基础上在比文献中更大的实例上计算高质量的独立集。

    Sep, 2015

  • 稀疏随机图上的半定规划及其在社区发现中的应用

    研究了 Erdos-Renyi 图和随机图在半定规划过程中的类似行为，用一些新的工具进行了证明，证明了 SDP 检测带有信息隐匿的随机图中的对称社区检测问题达到了信息论阈值。

    Apr, 2015

  • 在任意图上高效学习 Ising 模型

    本文探讨了如何通过简单的贪心算法来学习任意边界度数的 Ising 模型，在保证模型可辨识度的情况下，仅需用时 O (p^2) 即可还原图结构，并且该结构性质可独立运用于其他相关研究。

    Nov, 2014