- AAAI修改公平集群编辑
对于给定的图形应用 NP-hard Cluster Editing 问题的标准算法可能会产生偏向于数据子组（例如人口群体）的解决方案，我们提出了一种修改公平性约束条件，以确保每个子组的修改次数与其大小成比例，模型在现实社交网络上的经验分析表 - ICML坏策略密度：一种强化学习难度度量
本文提出了衡量强化学习难度的一种指标：坏策略密度，它衡量了在某个特定环境下，固定策略空间中低于某个阈值的策略的比例。同时，文章还证明了该指标有许多学习难度指标应该具备的性质。然而，完全计算该指标是 NP-hard 的，但是该指标也存在多项式 - 学习困难优化问题：数据生成的视角
本论文研究了通过机器学习解决 NP 困难问题的可行性，指出了训练数据的易变性及其对模型的影响，并提出了改进的方法来适应这个问题。该方法被应用于非线性、非凸、离散组合问题的求解，取得了有效的结果。
- 标记图上的蝴蝶核社区搜索
本文提出了一种新的问题，即基于具有不同标签的查询顶点的异构交叉社区查询，即蝴蝶芯社区 (butterfly-core community)，并证明该问题是 NP-hard 的。为了有效地解决这个问题，本文开发了一种启发式算法和一组高效的算法 - 时态图的边缘探索
研究了时间图的欧拉回路问题，发现即使对底层图的结构设置严格限制并且每条边只在三个时间段内被激活，确定给定的时间图是否具有时间欧拉性仍然是 NP 难问题，但是我们提出了一个新的参数 interval-membership-width，它的局限 - AAAI将强化学习与 Lin-Kernighan-Helsgaun 算法相结合解决旅行商问题
本文提出了一个基于增强学习的启发式算法 VSR-LKH，它运用 Q-learning、Sarsa、Monte Carlo 三种方法改进了已有的 TSP 算法 Lin-Kernighan-Helsgaun (LKH)，将其高效应用于 111 - MM使用答案集编程的稳定室友问题通用框架
介绍了 SRTI-ASP 这一 Answer Set Programming 的形式化框架，并使用其解决了 Stable Roommates problem 变体问题。
- 稀疏约束下的贝叶斯网络学习：参数化复杂度分析
本文研究在给定的约束条件下，学习最优贝叶斯网络的结构，其中最大程度为 1 的边界至少有距离 k，最大程度为 2 的边界以及具有大小至多为 c（c≥3）的连通分量的网络或其模糊化图的学习被证明是 NP 困难的，而在模糊化图中最多具有 k 个弧 - AAAI网络共享资源的防御
本文研究网络防御问题，针对节点之间的防御资源共享和边缘权重等因素，提出了两种多项式时间复杂度的算法以最小化因攻击带来的损失，分别为基于 LP 的算法和基于最大流的算法，并探讨了该问题的 NP-hard 性质及近似算法。
- 在带符号网络中发现极化社区
本文提出一种基于离散特征值问题的谱算法，以发现有极性社群的有符号网络中两个极化社群，证明所提出的问题是 NP-hard 的，同时在真实世界现象的情况下验证了算法的有效性并证明其比非平凡基线更好、更快、能够扩展到更大的网络。
- H - 自由图中最大权独立集问题的拟多项式时间逼近方案
本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。
- 计算最小持久环：多项式时间与困难问题
该研究讨论了计算拓扑持久图中持久循环的问题，通过识别两种特殊情况来使计算问题能够在多项式时间内解决，并发现了最小的持久循环能够捕捉数据的各种重要特征。
- DISCO: 影响力最大化遇上网络嵌入和深度学习
本文提出了 DISCO 框架，该框架集成了网络嵌入和深度强化学习技术以解决影响最大化问题。实验结果表明，相对于传统解决方案，DISCO 具有更好的效率和影响范围质量，并且表现出良好的通用性。
- 可扩展多匹配的高阶投影幂迭代
本文介绍了一种 Higher-Order Projected Power Iteration 方法来解决多目标匹配问题，能够在不限制问题规模的情况下处理几何一致性，并保证环一致性，实验结果表明该方法优于现有方法。
- NIPS成本感知因果图学习实验设计
研究了在给定因果图的情况下，通过最小成本干预变量来学习任意因果图的问题。证明了该问题是 NP 难问题，提出了一种基于贪心算法的常数级别近似解，并开发了一种计算干预设计的算法，该算法在稀疏因果图和干预条件下几乎是最优的，并讨论了在节点有成本的 - 时变旅行商问题的割、原始启发和学习分支
本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的 - 有界拉伸标记群体机器人重新配置的协同运动规划
该研究论文在协同运动规划和群体机器人方面取得了突破，提出了一种恒定算法以最小化协同平行运动计划的执行时间，并证明了最小执行时间的找到是 NP 难问题。
- 区间图的保距子图
本文探讨了无向、无权区间图中找到保持距离的小子图的问题，证明了对于一般图来说，找到最优距离保持子图是 NP-hard 问题；提出了一种求解区间图的近似算法，并且说明了存在区间图，其每个最优距离保持的子图都具有 O (k) 个引脚顶点和 Ω( - 多获胜者投票规则中的稳健性
研究了委员会选举结果对输入偏好顺序的微小变化的稳健性，探讨了不同投票规则的影响，发现单个偏好顺序内相邻候选人的一次交换可能导致最多一个委员会成员被替换或整个委员会被替换，并证明了计算导致选举结果改变的最小交换数通常是 NP-hard 的，但 - KDD在加权最大可满足性问题中逼近骨干
本文研究了加权最大可满足性问题中检索骨干的计算复杂度，并提出了一种基于骨干的局部搜索算法，称为 BGLS。实验结果表明，在质量和运行时间方面，BGLS 比现有算法表现更优异。