We present a progress on local computation algorithms for two coloring of $k$-uniform hypergraphs. We focus on instances that satisfy strengthened assumption of Local Lemma of the form $2^{1-\alpha k} (\Delta+1) e < 1$, where $\Delta$ is the bound on the maximum edge degree of the hypergraph. We discuss how previous works on the subject can be used to obtain an algorithm that works in polylogarithmic time per query for $\alpha$ up to about $0.139$. Then, we present a procedure that, within similar bounds on running time, solves wider range of instances by allowing $\alpha$ at most about $0.227$.
翻译：我们展示了本地计算算法的进展, 两个颜色为 $k$- unify 高光仪的本地计算算法。 我们关注的事例满足了本地 Lemma 强化的假设 : 2 ⁇ 1-\ alpha k} (\ Delta+1) e < 1 $, 其中$\ Delta$是高光谱最大边缘的定线 。 我们讨论如何利用以前关于这个主题的计算算法获得一种算法, 以每个查询的多元时间计算, 最多为 0.139 美元。 然后, 我们提出了一个程序, 在运行时间的类似范围内, 允许 $\ alpha$, 最多为 0. 227 美元, 解决范围更广的问题 。
相关内容
微信扫码咨询专知VIP会员