论文标题：Deterministic streaming algorithms for non-monotone submodular maximization

期刊：Frontiers of Computer Science

作者：Xiaoming SUN, Jialin ZHANG, Shuo ZHANG

发表时间：03 Sep 2024

DOI：10.1007/s11704-024-40266-4

微信链接：点击此处阅读微信文章

引用格式：

Xiaoming SUN, Jialin ZHANG, Shuo ZHANG. Deterministic streaming algorithms for non-monotone submodular maximization. Front. Comput. Sci., 2025, 19(6): 196404

阅读原文：

文章介绍

次模最大化是组合优化中的一个重要研究领域，具有广泛的实际应用价值。在大数据背景下，次模最大化问题的流算法设计受到了广泛关注。在该研究中，提出了一些专门针对非单调次模最大化问题的确定性流算法，提升了对应约束下算法的近似比。

该团队提出了一个流算法框架，该框架可以在少量读取数据的情况下，为非单调次模最大化问题提供近似解。该框架适用于多种不同的约束条件，并且在该框架下，算法在实时处理大规模数据集方面提高了近似比和效率，这是当今数据驱动的关键需求。

结果表明，该工作提出的方法在近似比表现上优于当前最先进的确定性算法，尤其是在传统方法难以处理的非单调次模最大化问题中表现尤为突出。

表1：非单调次模最大化问题在背包约束下的确定性流算法结果，其中本研究结果标为红色。

为了应对非单调目标函数下的次模最大化问题，该工作提出了基于阈值技术的流算法框架，并对该框架进行了修改，以调整为适用于不同约束的流算法版本。对于多维背包约束，他们使用了一种适用于单调情况的技术，对流算法框架进行了调整，该技术考虑到了单个大元素的情况，通过讨论调整阈值，最终获得确定性单次流算法。对于背包约束，他们的算法则对离线算法中用于单调次模最大化的算法进行了改进，通过在每一个贪心过程解中，枚举单个边际最大元素实现。最终，获得针对单背包约束的确定性多次流算法。

未来的研究可以探索将这些算法扩展到其他类型的约束条件。对于多维背包约束，大家更关注的问题是流算法的近似比是否可以进一步提高。而对于单背包约束，一个开放问题是，如何提升单次流算法近似比。当目标函数是非单调时，尽管这些算法改进了已知的最佳确定性算法，但其近似比仍然不如最佳随机算法。因此，填补这些差距将是一个非常有趣的研究方向。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn