• search hit 1 of 3
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.