Sort:
Open Access Issue
Two-Stage Submodular Maximization Under Knapsack Problem
Tsinghua Science and Technology 2024, 29(6): 1703-1708
Published: 20 June 2024
Abstract PDF (1.4 MB) Collect
Downloads:48

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 fj, j=1,2,,m, and each fj measures the similarity of each article in category j. We present a constant-approximation algorithm for this problem.

Total 1