TY - GEN A1 - Arulselvan, Ashwin T1 - A note on set union knapsack problem N2 - 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 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. KW - approximation KW - densest k-subgraph KW - set-union knapsack KW - greedy Y1 - 2012 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1020 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-10209 ER -