SCIENCE@home

Improved approximation algorithm for the Dense-3-Subhypergraph Problem

Amey Bhangale,R. Gandhi,G. Kortsarz

Published 2017 in arXiv.org

ABSTRACT

The study of Dense-$3$-Subhypergraph problem was initiated in Chlamt{\'{a}}c 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\in {\cal S}$ so that $S\subseteq 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(n^{0.69783..})$ by Chlamt{\'{a}}c et al. We improve this ratio to $n^{0.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(n^2/k^2)$ of Chlamt{\'{a}}c et al. We prove that under the {\em log density conjecture} (see Bhaskara et al. [STOC'10]) the ratio cannot be better than $\Omega(\sqrt{n})$ and demonstrate some cases in which this optimum can be attained.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    arXiv.org

  • Publication date

    2017-04-27

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1704.08620
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY