A note on the set union knapsack problem

Research output: Contribution to journalArticlepeer-review

39 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)214-218
Number of pages5
JournalDiscrete Applied Mathematics
Early online date17 Jan 2014
Publication statusPublished - 31 May 2014


  • approximation
  • densest k-subgraph
  • set-union knapsack
  • greedy


Dive into the research topics of 'A note on the set union knapsack problem'. Together they form a unique fingerprint.

Cite this