Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

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 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 (ε − 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 (m n) space. We present randomized single-pass algorithms that w.h.p.1 yield: • A 1 − ε approximation using O ˜ (n / ε 3) space and exponential post-processing time • A 3 / 4 − ε approximation using O ˜ (n / ε) 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 Ω (n k) 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 O ˜ (n 2 / ε 2) space algorithm, which is sublinear when m = ω (n) , that yields an α + ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2 f n approximation using O ˜ (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 Ω (m n) space. [ABSTRACT FROM AUTHOR]