在增量子模极大化问题中，我们关注在增加基数约束下的子模极大化，并寻求一种良好的增量解决方案，即一个地面集的排序，使得该排序的每个前缀都能为其相应的基数提供良好的解决方案。传统结果表明，贪心算法的竞争比率为 $\frac{\mathrm{e}}{\mathrm{e}-1} \approx 1.582$，在所有基数下都具有近似保证。此前没有更好的通用保证。我们提出了一种自适应缩放算法，其竞争比率达到了 $1.373$。此外，我们还补充了一个确定性的下界，表明增量子模极大化的最佳竞争比率至少为 $1.25$。
博主点评： 本文展示了增量子模极大化领域的最新突破，提出的新算法显著提高了竞争比率，相比传统贪心算法表现更优。这为相关应用提供了新的思路，特别是在处理大规模数据集时，优化算法的性能至关重要。