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 kk-subgraph problem on graphs of bounded degree.
|Number of pages||5|
|Journal||Discrete Applied Mathematics|
|Early online date||17 Jan 2014|
|Publication status||Published - 31 May 2014|
- densest k-subgraph
- set-union knapsack