论文标题
在常规统一超图中的独立集的随机贪婪算法，围绕着大周长
Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
论文作者
论文摘要
在本文中，我们考虑了一种$ r $ r $ robiform $ d $ d $ d $ gular hypergraphs $ g $的随机贪婪算法，$ n $ n $ vertices，带有girth $ g $。 By analyzing the expected size of the independent sets generated by this algorithm, we show that $α(G)\geq (f(d,r)-ε(g,d,r))n$, where $ε(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation.这扩展了Gamarnik和Goldberg的早期结果。我们还证明，将此算法应用于有界程度的均匀线性超图时，该算法浓缩物所产生的独立集的大小几乎可以肯定地在平均值上。
In this paper, we consider a randomized greedy algorithm for independent sets in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By analyzing the expected size of the independent sets generated by this algorithm, we show that $α(G)\geq (f(d,r)-ε(g,d,r))n$, where $ε(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and $r$, and $f(d,r)$ is determined by a differential equation. This extends earlier results of Gamarnik and Goldberg for graphs. We also prove that when applying this algorithm to uniform linear hypergraphs with bounded degree, the size of the independent sets generated by this algorithm concentrate around the mean asymptotically almost surely.
