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 |
