比较多元多项式函数全局优化算法,证明了使用具有半定规划的平方和松弛技术比代数方法更有效,并为实数代数几何中的广泛计算问题提供了可能性。
Mar, 2001
本文介绍了在凸多面体上计算多项式函数积分的算法和软件实现,并提供了基准计算结果。作者还展示了算法工具在组合投票理论中的应用。
Jul, 2011
本文提出一个快速和简单的算法来计算在标准单纯形三角形上的投影,利用 Moreau 恒等式,我们展示了该问题本质上是一元最小化问题,目标函数是严格凸的,且连续可微。此外,研究表明,最多有 n 个候选者可以明确计算,而最小化程序是唯一一个落入正确区间的程序。
Jan, 2011
探讨张量秩的计算复杂性,对任意整环上的张量证明了秩问题与该整环上的多项式方程组问题的多项式时间等价性,同时得出了对称秩和矩阵补全问题的类似结论。
Nov, 2016
简单算法的平滑分析有助于综合考虑最坏情况和平均情况下算法的预期性能,并且表明单纯形算法在平滑分析下具有多项式复杂性。
Nov, 2001
研究了有关各维热带超曲面交集的基本算法问题:判断此交集是否非空、是否为热带变量、是否连通,以及计算连接部分的数量。表明了输入数据的限制条件下可计算和硬计算之间的边界,并在不同的限制条件下证明了 NP-hardness 和 #P-hardness 结果,同时为其他不同限制条件提供了多项式时间算法。
Oct, 2004
我们提出了一种随机算法,它通过解决一小部分带有随机生成校验约束的离散组合优化问题,从而在高概率下能够得到可靠的常数近似值,从而有效地逼近离散图模型的分区函数。
Feb, 2013
本文考虑基于偏导数的一种复杂度度量,研究了计算偏导数空间维度的复杂性问题。作者使用轨迹方法给出了偏导数维度的合理下界,并留下了一个近似算法的开放问题。
Jul, 2016
我们证明采用最高的增益 / 负减少成本枢轴规则的单纯形法在确定性马尔科夫决策过程 (MDPs) 中收敛于强多项式时间,无论折扣因子如何。对于具有 n 个状态和 m 个动作的确定性 MDP,我们证明如果折扣因子是均匀的,则单纯形法需要 O (n^3m^2log^2 n) 次迭代,在每个动作都有不同折扣因子的情况下,它需要 O (n^5m^3log^2 n) 次迭代。
Aug, 2012
使用简单的代数论证了多项式函数在酉群、正交群和辛群上的 Haar 测度下的积分。得出了精确公式和渐近行为,并证明了 Haar 分布的正交和辛随机矩阵的渐近自由性以及类似 Itzykson-Zuber 积分的收敛性。
Feb, 2004