在计算机科学领域,稀疏非负卷积是计算两个长度为n的整数向量A和B卷积的核心问题,广泛应用于多个学科。它经常作为子程序出现在各种问题领域,如背包问题、k-SUM问题、所有对最短路径问题以及字符串模式匹配问题。在这些应用中,通常只需要计算非负向量的卷积。这个问题可以使用快速傅里叶变换在O(n log n)的时间内经典解决。
然而,在许多实际应用中,涉及的向量是稀疏的,因此期望存在与输出大小t相关的输出敏感算法来计算非负卷积。Muthukrishnan首先提出了这个问题,Cole和Hariharan在STOC '02会议上给出了一个近似线性时间的随机化算法。Chan和Lewenstein在STOC '15上提出了一个确定性算法,其运行时间比最优解多了2O(√log t·log log n)的时间复杂度,但前提是给出输出的较小超集;这个假设后来由Bringmann和Nakos在ICALP '21上移除。
本文首次提出了一种确定性的近似线性时间算法,用于计算稀疏非负卷积。这直接导致了输出敏感子集和问题、块质量模式匹配、N折布尔卷积等领域的最新确定性算法的改进,这些算法在处理这些问题时,与最快的已知随机化算法在对数因子上保持一致。我们的算法融合了代数和组合的思想和技术。
此外,我们还提供了两种快速的拉斯维加斯算法来计算稀疏非负卷积。具体来说,我们提出了一种简单的O(t log2 t)时间算法,作为Cole和Hariharan算法的一个可访问替代方案。随后,我们进一步发展了一种更高效的算法,其时间复杂度显著低于现有的解决方案,旨在提高效率和可靠性。
这些算法的贡献在于解决了确定性算法在处理稀疏数据时的效率问题,特别是在那些输出大小未知或难以预测的情况下。通过这些方法,我们可以更好地处理那些需要高效计算非负卷积的场景,例如在大规模数据集上的分析和处理任务。这些新的算法不仅在理论上有重要意义,而且对于实际应用中的性能提升也有着巨大的潜力。