Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
This addresses a fundamental optimization challenge in machine learning and AI, with applications in revenue maximization and image summarization, by providing efficient algorithms for a previously hard problem.
The paper tackles the problem of non-monotone submodular maximization under a knapsack constraint by introducing two algorithms, DLA and RLA, which achieve constant approximation factors of 6+ε and 4+ε respectively with linear query complexity of O(n log(1/ε)/ε).
This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size $n$ subject to a knapsack constraint, $\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm that provides an approximation factor of $6+ε$ while $\mathsf{RLA}$ is a randomized algorithm with an approximation factor of $4+ε$. Both run in $O(n \log(1/ε)/ε)$ query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.