- 从示例中学习线性时间公式的复杂性
本文探讨了学习线性时序逻辑 (LTL) 公式的计算复杂性，并构建了 LTL 的片段逼近算法，并对许多片段证明了 NP 完全性。
- 稀疏主成分分析的精确和近似算法
该论文提出了两种混合整数 SDP，用于优化选择主子矩阵的最大特征值，进一步分析和证明了它们的理论最优性差距优于现有技术，然后解决了在解决 MISDP 时存在的计算难题，同时提出了近似算法和 MILP 模型，有效地解决了规模问题，最后将其扩展 - 通过公平的群组表达进行公平聚类
本文研究了公平聚类的结构、计算及近似算法，并提出了群组代表性聚类的思想，旨在解决公平聚类与聚类代表性之间的矛盾问题。
- 分层聚类：0.585 收益近似
本研究考虑采用收益目标函数的双重问题，并证明了存在一种双重算法（经过半切）的近似解，得到了广义收益问题的 0.585 近似算法，从而改进了此前由一系列早期研究导致的 0.4246 近似保证。
- 用于可解释性的生成可证明近似最优的聚类描述符的高效算法
本文研究如何提高机器学习方法结果的可解释性，探讨了通过构建对聚类进行简洁表示的方法，提出了可证明性能保证的近似算法，并应用于基因组序列的不同威胁级别的聚类解释。
- 公平相关聚类
本研究探讨了在公平约束下的相关性聚类，通过引入新的组合优化问题，在多种公正性约束条件下，获得了公平相关聚类的近似算法。同时，通过对真实图形的算法进行深入分析，表明与现有的不公平算法相比，可以在有限的成本增加下获得相关聚类的公平解决方案。
- ICML基于群体决策离散选择模型的选择集优化
本文基于离散选择建模，针对整体权衡、最大化一致性或不一致性以及促进特定选择等问题，提出了一种优化框架，着重研究了直接更改选择集合对决策者群体偏好的影响，通过限制条件的引入，揭示了不同问题之间的基本边界，为难以解决的问题设计了近似算法，并展示 - AAAI确定性马尔科夫决策过程中计算状态相似性的可扩展方法
本文针对 MDPs 中 Bisimulation Metrics 的计算提出了新的算法，包括适用于连续状态 MDP 的可微损失函数，其中第一算法通过采样保证收敛性，第二算法通过学习实现了对大规模、确定性 MDP 的近似计算。
- 关于多边际最优输运近似复杂度的研究
本文研究了多项式最优运输（MOT）距离的近似复杂性，提出了两个新的确定性算法：多重边缘 Sinkhorn 算法和加速多重边缘 Sinkhorn 算法。通过实验，证明了这两种算法在计算效率和准确性上的优越性。
- 最优输运的图论加法逼近
本文提出了一种基于 Gabow 和 Tarjan 的图算法的新颖分析，并提供了一个简单的贪婪式迭代算法，其执行时间为 O (n^2*C/δ + nC^2/δ^2)，用于求解概率分布的最优运输问题，在数值不稳定的情况下具有竞争力的执行时间。
- 组合问题的图神经网络的近似比
该论文从理论角度研究了如何利用图神经网络解决组合问题的近似算法，并提出了一种新的 GNN 类别，揭示了 GNN 的相对近似比，并证明了在节点特征中添加染色可以提高学习算法的近似比。
- 图算法的平均灵敏度
对图算法的平均敏感度进行系统研究，并提供了具有低平均敏感度的近似算法，其中主要应用了局部计算算法和已知次线性时间算法的分析方法。
- 数据流中的相关聚类
本文研究动态数据流模型下相关聚类问题，结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法，解决了自然问题。
- 最小范数和有序优化问题的近似算法
本文研究最小范数优化问题，通过引入常用的单调对称范数，相较于已有的算法，针对负载均衡和聚类等实际问题，提出了一套通用且高效的解决方案，并在此基础上给出了一些近似算法。
- AAAI在最优因子范围内找到所有贝叶斯网络结构
提出了一种基于近似算法的模型平均方法，该方法仅考虑可靠的模型且能在数据量较大的情况下高效地进行比较。
- 关于 (稀疏) 覆盖整数规划问题的近似算法
本文针对覆盖整数规划问题提出了基于随机取整与修改的简单算法来改进其逼近度，并证明了近似度几乎是最优的，并且在没有失去逼近保证或效率的情况下可以去随机化，同时也提出了一种基于强化的线性规划近似方案，其运行时间比之前的最优解快 n 倍。这两个算 - 鲁棒组合优化的随机化策略
本文研究了一类鲁棒优化问题，提出了两种设计逼近算法的方案，一种适用于线性目标函数的问题，另一种则基于乘性权重更新方法，并证明了这些算法在特定条件下具有不错的逼近比例，可用于求解离散优化问题中的独立集、子模函数等问题。
- 快速最大化整数晶格上的非次模、单调函数
该论文提出了两种多项式查询复杂度的逼近算法来最大化整数格上的非子模函数，同时提出了一个广义影响力最大化框架来推广之前的研究，并在此背景下展示了我们算法的高效性。
- 公平分簇
本文研究了如何在保护隐私的前提下实现公平聚类，提出了公平小集（fairlets）的概念，并基于最小代价流设计出高效的近似算法，在实际数据集中验证了公平聚类的价值。
- ICML计算最优传输：加速梯度下降比 Sinkhorn 算法更好的复杂度
本研究分析了逼近两个离散分布之间的一般最优运输（OT）距离的两种算法，并证明了复杂度界限，其中一种基于 Sinkhorn 算法，另一种基于 Adaptive Primal-Dual Accelerated Gradient Descent