Revisiting Maximum Satisfiability and Related Problems in Data Streams
share
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 Ω(√(n)) space is necessary to yield a √(2)/2+ϵ approximation of the optimum value; they also presented an algorithm that yields a √(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 Õ(n/ϵ^3) space and exponential post-processing time and 2) A 3/4-ϵ approximation using Õ(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.
READ FULL TEXT