论文标题
重新访问数据流中最大的满意度和相关问题
Revisiting Maximum Satisfiability and Related Problems in Data Streams
论文作者
论文摘要
我们在数据流模型中重新审视MAXSAT问题。在此问题中，该流由$ M $ $条款组成，这些条款是从$ n $ boolean变量中绘制的文字的析取。目的是找到最大化满意子句数量的变量的分配。 Chou等。 （focs 2020）表明$ω（\ sqrt {n}）$ space对于产生最佳值的$ \ sqrt {2}/2+ε$近似；他们还提出了一种算法，该算法使用$ o（\ log n/ε^2）$ space产生了最佳值的$ \ sqrt {2}/2-ε$近似。 在本文中，我们不仅专注于近似最佳值，而且还致力于使用Sublinear $ O（MN）$ Space获得相应的布尔分配。我们提出了W.H.P.的随机单通行算法收益率：1）使用$ \ tilde {o}（n/ε^3）$ 1-ε$近似值，使用$ \ tilde {o}（o}（n/ε）$空间和多态后处理时间。我们的想法也扩展到动态流。另一方面，我们表明，流式KSAT问题要求确定是否可以满足所有尺寸-K $输入条款条款必须使用$ω（n^k）$ space。 我们还考虑在这种情况下其他相关问题。
We revisit the MaxSAT problem in the data stream model. In this problem, the stream consists of $m$ clauses that are disjunctions of literals drawn from $n$ Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that $Ω(\sqrt{n})$ space is necessary to yield a $\sqrt{2}/2+ε$ approximation of the optimum value; they also presented an algorithm that yields a $\sqrt{2}/2-ε$ approximation of the optimum value using $O(\log n/ε^2)$ space. In this paper, we focus not only on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear $o(mn)$ space. We present randomized single-pass algorithms that w.h.p. yield: 1) A $1-ε$ approximation using $\tilde{O}(n/ε^3)$ space and exponential post-processing time and 2) A $3/4-ε$ approximation using $\tilde{O}(n/ε)$ space and polynomial post-processing time. Our ideas also extend to dynamic streams. On the other hand, we show that the streaming kSAT problem that asks to decide whether one can satisfy all size-$k$ input clauses must use $Ω(n^k)$ space. We also consider other related problems in this setting.
