k-Submodular Maximization Under Individual Knapsack Constraints: Applications and Streaming Algorithm
- 15 July 2025
- journal article
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 43 (04)
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.Keywords
Funding Information
- Vingroup Innovation Foundation (VINIF.2024.TS.069)
This publication has 23 references indexed in Scilit:
- Improved approximation algorithms for -submodular maximization under a knapsack constraintComputers & Operations Research, 2023
- Non-monotone k-Submodular Function Maximization with Individual Size Constraints2023
- Maximizing k-submodular functions under budget constraint: applications and streaming algorithmsJournal of Combinatorial Optimization, 2022
- On maximizing a monotone k-submodular function under a knapsack constraintOperations Research Letters, 2022
- Streaming Algorithms for Budgeted k-Submodular Maximization Problem2021
- Importance Sample-Based Approximation Algorithm for Cost-Aware Targeted Viral Marketing2019
- Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack ConstraintAlgorithmica, 2019
- On maximizing a monotone -submodular function subject to a matroid constraintDiscrete Optimization, 2017
- Submodular maximization meets streaming: matchings, matroids, and moreMathematical Programming, 2015
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978