A note on the set union knapsack problem

作者：Arulselvan Ashwin^*

来源：Discrete Applied Mathematics, 2014, 169: 214-218.

DOI：10.1016/j.dam.2013.12.015

• Approximation
• Densest k-subgraph
• Set-union knapsack
• Greedy

Recently, Khuller, Moss and Naor presented a greedy algorithm for the budgeted maximum coverage problem. In this note, we observe that this algorithm also approximates a special case of a set-union knapsack problem within a constant factor. In the special case, an element is a member of less than a constant number of subsets. This guarantee naturally extends to densest k-subgraph problem on graphs of bounded degree.

• 出版日期2014-5-31