Documents
Presentation Slides
Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations
- Citation Author(s):
- Submitted by:
- Qilian Yu
- Last updated:
- 2 December 2016 - 10:41pm
- Document Type:
- Presentation Slides
- Document Year:
- 2016
- Event:
- Presenters:
- Qilian Yu
- Paper Code:
- 1301
- Categories:
- Log in to post comments
Submodular maximization problems belong to the family of combinatorial optimization problems and enjoy wide applications. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a d-knapsack constraint, for which we propose a streaming algorithm that
achieves a (1/1+2d − ε) -approximation of the optimal value,
while it only needs one single pass through the dataset without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via an application in scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.