A note on the set union knapsack problem. (English) Zbl 1288.05177

Summary: Recently, S. Khuller et al. [Inf. Process. Lett. 70, No.1, 39–45 (1999; Zbl 1002.68203)] 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 \(k\)-subgraph problem on graphs of bounded degree.


05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C42 Density (toughness, etc.)
90C10 Integer programming
68W25 Approximation algorithms


Zbl 1002.68203
Full Text: DOI


[1] Feige, U.; Kortsarz, G.; Peleg, D., The dense \(k\)-subgraph problem, Algorithmica, 29, 2001, (1999)
[2] Goldschmidt, O.; Nehme, D.; Yu, G., Note: on the set-union knapsack problem, Naval Res. Logist. (NRL), 41, 6, 833-842, (1994) · Zbl 0831.90088
[3] M.T. Hajiaghayi, K. Jain, K. Konwar, L.C. Lau, I.I. Măndoiu, A. Russell, A. Shvartsman, V.V. Vazirani, The minimum \(k\)-colored subgraph problem in haplotyping and DNA primer selection, in: Proc. Int. Workshop on Bioinformatics Research and Applications, IWBRA, 2006.
[4] Khuller, S.; Moss, A.; Naor, J., The budgeted maximum coverage problem, Inform. Process. Lett., 70, 39-45, (1999) · Zbl 1002.68203
[5] Prasad Raghavendra, David Steurer, Graph expansion and the unique games conjecture, in: STOC, 2010, pp. 755-764. · Zbl 1293.05373
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.