Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 214-218 |
| Number of pages | 5 |
| Journal | Discrete Applied Mathematics |
| Volume | 169 |
| Early online date | 17 Jan 2014 |
| DOIs | |
| Publication status | Published - 31 May 2014 |
Keywords
- approximation
- densest k-subgraph
- set-union knapsack
- greedy