Improved approximation algorithm for the Dense-3-Subhypergraph Problem

The study of Dense-3-Subhypergraph problem was initiated in Chlamt'ac et al. [Approx'16]. The input is a universe U and collection cal S of subsets of U, each of size 3, and a number k. The goal is to choose a set W of k elements from the universe, and maximize the number of sets, S∈ cal S so that Ssubseteq W. The members in U are called em vertices and the sets of cal S are called the em hyperedges. This is the simplest extension into hyperedges of the case of sets of size 2 which is the well known Dense k-subgraph problem. The best known ratio for the Dense-3-Subhypergraph is O(n0.69783..) by Chlamt'ac et al. We improve this ratio to n0.61802... More importantly, we give a new algorithm that approximates Dense-3-Subhypergraph within a ratio of tilde O(n/k), which improves the ratio of O(n2/k2) of Chlamt'ac et al. We prove that under the em log density conjecture (see Bhaskara et al. [STOC'10]) the ratio cannot be better than Omega(√n) and demonstrate some cases in which this optimum can be attained.