Name
Abstract | ||
|---|---|---|
study of Dense-$3$-Subhypergraph problem was initiated in Chlamt{u0027{a}}c et al. [Approxu002716]. input is a universe $U$ and collection ${cal S}$ of subsets of $U$, each of size $3$, and a number $k$. goal is to choose a set $W$ of $k$ elements from the universe, and maximize the number of sets, $Sin {cal S}$ so that $Ssubseteq W$. 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{u0027{a}}c et al. 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{u0027{a}}c et al. We prove that under the {em log density conjecture} (see Bhaskara et al. [STOCu002710]) the ratio cannot be better than $Omega(sqrt{n})$ and demonstrate some cases in which this optimum can be attained. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Data Structures and Algorithms | Approximation algorithm,Discrete mathematics,Combinatorics,Vertex (geometry),Approx,Omega,Universe,Conjecture,Mathematics |
DocType | Volume | Citations |
Journal | abs/1704.08620 | 0 |
PageRank | References | Authors |
0.34 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amey Bhangale | 1 | 10 | 6.71 |
| Rajiv Gandhi | 2 | 445 | 24.52 |
| Guy Kortsarz | 3 | 1539 | 126.16 |