.png){kind=icon}
.png){kind=icon}
Return
Two-Stage Submodular Maximization Under Knapsack Problem
.png){kind=icon}
PRE
AI
DOI：10.26599/TST.2023.9010107.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization. In this paper, we consider knapsack constraint. In this problem, we give n articles and m categories, and the goal is to select a subset of articles that can maximize the function F(S). Function F(S) consists of m monotone submodular functions f(j), j=1,2, ..., m, and each f(j) measures the similarity of each article in category j. We present a constant-approximation algorithm for this problem.
Keywords:
Machine learning
Approximation algorithms
Optimization
submodular function
knapsack constraint
matroid
Journal
T
IF:
3.5
Papers:
987
Citations:
2.5K
Organization
View more organizations