- 简化谱半径以控制流行病传播的近似算法
本文提出了一套可证明的逼近算法,通过删除最小成本的边(建立隔离区)或节点(建立疫苗接种)来减少网络的谱半径,主要算法基于敲定特定长度封闭路径的思想,性能较之前的启发式算法更优,实验证明了算法的可行性和解的属性。
- 非交换格罗滕迪克问题的严密度
证明了使用迹范数的矩阵空间中的 $L_2$ 嵌入可以得到非交换 Grothendieck 问题的近似传递性,从而说明了使用 Naor, Regev 和 Vidick 算法的近似率是最优的,并且证实了对于交换的 Little Grothend - 完全图和完全 k 部分图上相关聚类的近似最优线性规划舍入算法
该论文提出了一种新的线性规划松弛四舍五入方案,解决了相关聚类问题的近似算法问题和完整性间隙问题,从而在完全图中实现了 2.06-ε 的近似度,而在完全 $k$- 部分图中实现了 3 的近似度。
- AAAIPOMDP 中的最优成本几乎确定可达性
本文研究部分可观察马尔可夫决策过程 (POMDPs),带有一组目标状态并且每个转移都有一个整数成本。研究的最优化目标是在确保(概率为 1)几乎达到目标集时最小化预期总成本。我们证明,对于整数成本,近似最优成本是不可判定的。对于正成本,我们的 - 混合装箱 / 覆盖和设施选址线性规划的近线性工作算法
本文介绍了一种高效的线性规划和设施选址的近似算法,同时提出了一种节省时间和工作量的并行算法,该算法可在多项式对数时间内完成,并在时间和工作方面提供了(1+ϵ)- 近似解。
- 受限曲率下次模优化和超模优化的最优逼近
论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题,特别地,当目标函数有闭合总曲率时,获得了一个 (1-c/e)- 近似的结果;该算法基于连续贪心算法和非随机局部搜索的修改,并进行了扩展以包括在一些特定场景下的应用,例 - 熵、优化与计数
研究计算基于观测边际的离散对象的最大熵分布的问题,研究表明在一般条件下存在着多项式大小的描述,给出了一些关于近似计算和计数最大熵分布的算法,并且阐明了计算最大熵分布和计算数量之间的等价性。
- 以资源分配为全比例代表制:可接近度结果
通过模拟 Monroe 及 Chamberlin 和 Courant 多胜者投票系统,将其建模为某种资源分配问题,研究发现在许多限制情况下,难以使用常数因子逼近算法进行优化,但也存在使用 Borda 得分优化总选民满意度的情况下,能够实现良 - 正半定规划的更快速、更简单的宽度独立并行算法
本文研究了正半定规划的近似算法,提出了一种简单的 NC 并行算法,其迭代次数为 O (1/ϵ³ log³ n),总工作量近似为因子分解中非零条目数的线性级别。
- 矩阵子集选择及应用的加速
本文研究了一种矩阵的子集选择问题,其中关注了 Frobenius 范数和谱矩阵范数,并提出了多种新的逼近算法,并证明了在常数因子范围内逼近度是最优的,并且阐述了在一个无向图中找到低拉伸生成树的组合问题与矩阵子集选择问题之间的对应关系及其各种 - 快速平衡划分尽管在网格和树上也很困难
本文探讨了 k-Balanced Partitioning 问题的两类近似算法:快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明,这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架,以证明了该问 - MAP 解释的复杂性结果和逼近策略
研究了贝叶斯网络中 MAP 问题的复杂性,发现即使 MPE 和 Pr 可以轻松计算,MAP 仍然很难。为了找到一个接近最优解的算法,提出了一种通用的 MAP 近似框架,并给出了两个具体的实现,用于对那些即使 Pr 和 MPE 都难以计算的网 - 随机组合优化问题的期望效用最大化
该研究考虑了一类随机组合优化问题,其中输入数据集中的元素权重不确定,并提出了一种基于预期效用的解决方案,以最大化某些给定实用函数的预期效益,并证明了在问题的精确版本下,可以针对几种重要的实用函数类得到多项式时间逼近算法。
- 来自精确采样的流算法
该研究提出了一种名为 Precision Sampling 的概率性方法来解决一系列数据流算法问题,包括向量构图、重量估算以及求不同范数的估值,同时也能够很好地解决估值的精度问题。
- 通过近似特征向量计算隐式实现正则化
本文研究了使用近似算法进行图拉普拉斯算子的最小非平凡特征向量计算中,隐式正则化过程的应用,同时阐述了相关优化问题。
- 网络社群检测算法实证比较
本文探讨了一些网络社区检测方法,比较它们的性能和系统偏差;评估了用于形式化网络社区概念的几种常见目标函数,并研究了几种旨在优化这些目标函数的近似算法。此外,本论文还考虑了问题的大小解决版本,从社区大小的角度来考虑社区质量,以更好地检验社区检 - 匿名博弈中的均衡计算
该研究提出了一种高效的近似算法,适用于在匿名游戏中寻找纳什均衡,其中玩家的效用虽然不同,但在其他玩家之间没有区别,该算法适用于玩家众多但策略较少的游戏,可在多项式时间内计算出近似的 “纯纳什均衡”,此近似值的上限是 O (s^2L),此外, - 混合装箱和覆盖的顺序和并行算法
本文研究线性规划、近似算法和贪心算法在解决混合装箱和覆盖问题方面的应用,并提出一种可行的贪心算法,该算法复杂度为 O (epsilon^-2 log m) 线性时间迭代,且结论推广了之前的研究结果。