Journal
DISCRETE APPLIED MATHEMATICS
Volume 169, Issue -, Pages 214-218Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2013.12.015
Keywords
Approximation; Densest k-subgraph; Set-union knapsack; Greedy
Categories
Funding
- DFG research center Matheon Mathematics for key technologies in Berlin.
Ask authors/readers for more resources
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 k-subgraph problem on graphs of bounded degree. (C) 2014 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available