Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations

Abstract: 

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.

up
0 users have voted:

Paper Details

Authors:
Qilian Yu, Easton Li Xu, Shuguang Cui
Submitted On:
2 December 2016 - 10:41pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Qilian Yu
Paper Code:
1301
Document Year:
2016
Cite

Document Files

Lecture Slides

(190 downloads)

Subscribe

[1] Qilian Yu, Easton Li Xu, Shuguang Cui, "Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations", IEEE SigPort, 2016. [Online]. Available: http://sigport.org/1336. Accessed: Apr. 19, 2018.
@article{1336-16,
url = {http://sigport.org/1336},
author = {Qilian Yu; Easton Li Xu; Shuguang Cui },
publisher = {IEEE SigPort},
title = {Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations},
year = {2016} }
TY - EJOUR
T1 - Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations
AU - Qilian Yu; Easton Li Xu; Shuguang Cui
PY - 2016
PB - IEEE SigPort
UR - http://sigport.org/1336
ER -
Qilian Yu, Easton Li Xu, Shuguang Cui. (2016). Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations. IEEE SigPort. http://sigport.org/1336
Qilian Yu, Easton Li Xu, Shuguang Cui, 2016. Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations. Available at: http://sigport.org/1336.
Qilian Yu, Easton Li Xu, Shuguang Cui. (2016). "Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations." Web.
1. Qilian Yu, Easton Li Xu, Shuguang Cui. Submodular Maximization with Multi-Knapsack Constraints and its Applications in Scientific Literature Recommendations [Internet]. IEEE SigPort; 2016. Available from : http://sigport.org/1336