Abstract
The [ ]-submodular optimization problems have been an active research area with many applications in machine learning, such as data summarization, influence maximization, and maximum revenue. In this work, we investigate the problem of [ ]-submodular maximization under individual knapsack constraints ([ ]) that capture various realities of such applications. We solve the problem in a streaming setting that requires two passes over the data and a reasonable amount of memory. In particular, we propose a streaming algorithm named [ ][ ]which runs in [ ] query complexity, takes [ ] space complexity, and achieves an approximation ratio of [ ] for monotone objective function; [ ] for the non-monotone objective function, where [ ] is the size of the ground set, [ ] is the total budget and [ ] is an input parameter. We validate our algorithm in two applications of the studied problem, including revenue maximization and sensor placement on some benchmark datasets. The experimental results show that our streaming algorithm provides higher-quality solutions with lower query complexity than the existing baseline algorithm.
Funding Information
  • Vingroup Innovation Foundation (VINIF.2024.TS.069)