论文标题
所有Boolean Max-2csps和Max-ksat的最佳流近似值
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
论文作者
论文摘要
我们证明了流模型中所有Boolean Max-2CSP问题的近似值的上限和下限。具体而言，对于每种类型的Max-2CSP问题，我们都会给出一个明确的常量$α$，s.t。对于任何$ε> 0 $（i），使用space $ o（\ log {n}）$的$（α-ε）$ - 流近似； （ii）任何$（α+ε）$ - 流近似需要空间$ω（\ sqrt {n}）$。这概括了[Kapralov，Khanna，Sudan Soda 2015； Kapralov，Krachun Stoc 2019]，他表明最高切割的最佳近似值为$ 1/2 $。 在这项工作之前，确定所有其他Max-2CSP的比率的问题均已开放。对于某些特定的MAX-2CSP，我们的结果令人惊讶。对于最大速率问题，上限为$ 1/2 $的上限与$ 2/5 $的下限[Guruswami，Velingker，Velusamy大约2017年]。我们表明，这些界限都不紧密，最大值的最佳比率为$ 4/9 $。我们还确定Max-2sat的紧密近似值是$ \ sqrt {2}/2 $，并且对于Max-2sat，它是$ 3/4 $。作为副产品，我们的结果在Max-2sat和精确的Max-2sat的空间效率近似之间给出了分离。这与多项式空间的多项式时间算法的设置形成鲜明对比，在多项式空间中，这两个问题也很难近似。最后，我们证明\ mksat {}的紧密流近似为$ \ sqrt {2}/2 $对于每个$ k \ geq2 $。
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant $α$, s.t. for any $ε>0$ (i) there is an $(α-ε)$-streaming approximation using space $O(\log{n})$; and (ii) any $(α+ε)$-streaming approximation requires space $Ω(\sqrt{n})$. This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was $1/2$. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DCUT problem, there was a gap between an upper bound of $1/2$ and a lower bound of $2/5$ [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DCUT is $4/9$. We also establish that the tight approximation for Max-2SAT is $\sqrt{2}/2$, and for Exact Max-2SAT it is $3/4$. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for \mksat{} is $\sqrt{2}/2$ for every $k\geq2$.
