A note on set union knapsack problem
Please always quote using this URN:urn:nbn:de:0296-matheon-10209
- 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.
Author: | Ashwin Arulselvan |
---|---|
URN: | urn:nbn:de:0296-matheon-10209 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2012/01/25 |
Release Date: | 2012/01/25 |
Tag: | |
Institute: | Technische Universität Berlin |
MSC-Classification: | 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Rxx Discrete mathematics in relation to computer science / 68R01 General |
Preprint Number: | 872 |