| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419066 | Discrete Applied Mathematics | 2014 | 5 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ashwin Arulselvan,