本文主要介绍了 Carathéodory's 定理的近似版本及其算法应用，特别是对于 bimatrix game Nash equilibrium 和稠密子图问题的多项式时间级别的近似算法。

Jun, 2014

通过使用标准约减和新技术的混合方法，我们改进了查找凸集中点的运行时间，同时提高了在连续和组合优化中的算法性能，特别是子模规划和半定规划问题。

Aug, 2015

ell_p 子空间逼近问题是一个 NP-hard 的低秩逼近问题，我们通过构建一个强核心集算法，第一次获得了对于 rank 参数 k 几乎最优性的依赖，得到了 p<2 时的近似线性边界 O (k) poly (ε^(-1)) 和 p>2 时的 O (k^(p/2)) poly (ε^(-1)) 边界，此外，我们还解决了在线 setting 中 poly (k) 因子损失的问题。

Jul, 2024

论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题，特别地，当目标函数有闭合总曲率时，获得了一个 (1-c/e)- 近似的结果；该算法基于连续贪心算法和非随机局部搜索的修改，并进行了扩展以包括在一些特定场景下的应用，例如最大熵抽样和列子集选择问题。

Nov, 2013

研究了多维欧氏空间中寻找一个 k 维子空间 F，使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()（如 Huber 和 Tukey 损失函数）下此问题的最优解。这些鲁棒子空间可替代奇异值分解（SVD）提供更有效的解决方案，对于典型的 M-Estimators，对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。

Oct, 2015

本文提出了一种基于采样技术和新的乘性更新算法的新颖子线性时间逼近算法，可用于解决一些机器学习优化问题，如训练线性分类器和查找最小包含球，此外，还用于解决一些核化版本的这些问题，如 SVM 等。此外，文章还在半流数据流设置中给出了实现，实现了第一个低通多项式空间和次线性时间算法。

Oct, 2010

提出了一种基于组合数学的算法，用于求解在一个制约性匹配中的单调子模优化问题，算法具有很高的精度和时间效率。

Apr, 2012

本文从大规模消耗能源问题出发，对 mAP 米级别的近似精度提出解决方案，同时研究了深度的语义信息和有限的上下文信息如何影响计算性能。

Jul, 2015

该研究提出了一种在 oracle 模型下，用高斯凸优化问题的 $p$ 阶 Taylor 拓展在查询点处获得的方法，可以实现任意 $p$ 阶导数为 Lipschitz 的凸函数的收敛速率 $\tilde {O}(1/k^{(3p+1)/2})$。

Dec, 2018

提出一种用于最大化满足背包限制下单调子模函数的算法，并且该算法的多项式时间复杂度为一个取决于输入函数曲率 c 的比率，该算法的近似度为 1-c/e-ε，这一近似度对于任何处于区间 [0,1] 中的 c 值均是紧确的。此外，该研究提供了用于预算分配问题的多项式时间算法，并且有一种更好的近似度。

Jul, 2016