Deterministic streaming algorithms for non-monotone submodular maximization

Submodular maximization is a significant area of interest in combinatorial optimization, with numerous real-world applications. A research team led by Xiaoming SUN from the State Key Lab of Processors at the Institute of Computing Technology, Chinese Academy of Sciences, published their new research on 15 June 2025 in Frontiers of Computer Science, co-published by Higher Education Press and Springer Nature. The study introduces deterministic streaming algorithms that are specifically designed to handle non-monotone submodular maximization, a challenging problem that has yet to be effectively addressed by existing methods.

The team developed a streaming algorithm framework that provides deterministic solutions for the d-knapsack and knapsack constraints under non-monotone objective functions. These algorithms offer improved approximation ratios and efficiency in processing massive datasets in real-time—key requirements in today’s data-driven world.

In their research, the team presents a 1-pass deterministic streaming algorithm for the d-knapsack constraint, which achieves a 1/(4(d + 1)) – ε approximation ratio. The algorithm requires O(BlogB/ε) memory and O(logB/ε) query time per element, where B is the maximum number of elements the d-knapsack can store.

Furthermore, the team proposed a multi-pass streaming algorithm for the knapsack constraint, which achieves a 1/6 – ε approximation ratio. This algorithm performs multiple passes over the data, storing O(B) elements and making O(logB/ε) queries per element.

The innovation lies in the algorithm’s ability to process large-scale, streaming data efficiently while providing stronger performance guarantees than existing approaches. The results show that the proposed methods outperform current state-of-the-art algorithms in approximation ratios, particularly in non-monotone settings where traditional approaches struggle. 

To address the submodular maximization problem with non-monotone objective functions, they propose a streaming algorithm framework based on an offline greedy algorithm. They modify this framework to create different versions of the streaming algorithms that are customized to different constraints. For the d-knapsack constraint, they modify the streaming framework with a technique from for the monotone case, which takes into account the large single element. For the knapsack constraint, their algorithm modifies the technique from the Greedy+Max algorithm in the offline setting for the monotone submodular maximization subject to the knapsack constraint.

Future research could explore extending these algorithms to other types of constraints. For the d-knapsack constraint, the question is whether the approximation ratio of the streaming algorithm can be further improved.  As for the single knapsack constraint, there is an unresolved issue on how to enhance the approximation of 1-pass streaming algorithms. When the objective function is non-monotone, though these algorithms improve the best-known deterministic algorithms, their approximation ratios are still worse than the best randomized algorithms. It is very interesting to fill these gaps.