Approximations of the Densest k-Subhypergraph and Set Union Knapsack problems

Abstract: For any given

e p s i l o n > 0

we provide an algorithm for the Densest

k

-Subhypergraph Problem with an approximation ratio of at most

O (n^{h e t a_{m} + 2 e p s i l o n})

for

h e t a_{m} = f r a c 12 m - f r a c 12 - f r a c 1 2 m

and run time at most

O (n^{m - 2 + 1 / e p s i l o n})

, where the hyperedges have at most

m

vertices. We use this result to give an algorithm for the Set Union Knapsack Problem with an approximation ratio of at most

O (n^{a l p h a_{m} + e p s i l o n})

for

a l p h a_{m} = f r a c 23 [m - 1 - f r a c 2 m - 2 m^{2} + m - 1]

and run time at most

O (n^{5 (m - 2) + 9 / e p s i l o n})

, where the subsets have at most

m

elements. The author is not aware of any previous results on the approximation of either of these two problems.

This page was built for publication: Approximations of the Densest k-Subhypergraph and Set Union Knapsack problems