期刊
THEORETICAL COMPUTER SCIENCE
卷 982, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.tcs.2023.114271
关键词
Data streams; Algorithms; Maximum satisfiability; Lower bounds
This paper addresses the maximum satisfiability problem in the data stream model. It presents algorithms that achieve approximations to the optimum value and corresponding Boolean assignments in sublinear space complexity. The paper also discusses related problems and provides approximation algorithms and space complexity for them.
We revisit the maximum satisfiability problem (Max-SAT) 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 root of satisfied clauses. Chou et al. (FOCS 2020) showed that omega( n) space is necessary to yield a root root 2/2 +e approximation of the optimum value; they also presented an algorithm that yields a 2/2 - e approximation of the optimum value using O(e-2 log n) space. In this paper, we not only focus 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.1 yield:center dot A 1 - e approximation using Õ(n/e3) space and exponential post-processing time center dot A 3/4 - e approximation using Õ(n/e) space and polynomial post-processing time.Our ideas also extend to dynamic streams. However, we show that the streaming k-SAT problem, which asks whether one can satisfy all size -k input clauses, must use omega(nk) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a Õ(n2/e2) space algorithm, which is sublinear when m = co(n), that yields an a +e approximation where a is the approximation guarantee of the offline root algorithm. If each variable appears in at most f clauses, we show that a 2 fn approximation using Õ(n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use omega(mn) space.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据