引用visarga · 2017-11
“This arXiv paper shows the STOA from 2015:”
指出这篇 arXiv 论文给出了 2015 年的子集和问题最优算法
给出比标准动态规划更快的子集和伪多项式算法
给定 n 个正整数的多重集合 S 和目标整数 t,论文提出一种分治算法,能在 Õ(min{√n·u, u^{4/3}, σ}) 时间内算出所有不超过 u 的可达子集和,优于标准动态规划的 O(nu),据作者所知是该问题最快的通用算法。作者还给出针对循环群的变体,在 Õ(min{√n·m, m^{5/4}}) 时间内算出群内所有可达的子集和。
评论者引用它作为 2015 年子集和问题伪多项式时间算法的最新进展。
“This arXiv paper shows the STOA from 2015:”