# Improved approximation algorithm for the Dense-3-Subhypergraph Problem

arXiv: https://arxiv.org/abs/1704.08620 · HTML: https://mlsanity.com/paper/1704.08620/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2017.

## Built on by (most cited first, 3 of 3)

- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Information Limits for Detecting a Subhypergraph](https://mlsanity.com/paper/2105.02259/) (2021)

## Abstract (arXiv)

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.