A parallel approximation algorithm for the MAXIMUM 2-CNF SATISFIABILITY problem is presented. This algorithm runs in O( log 2 (n + |F|)) parallel time on a CREW PRAM machine using O(n + |F|) processors, where n is the number of variables and |F| is the number of clauses. Performance guarantees are considered for three slightly differing definitions of this problem.
No takes yet. Share an insight, caveat, or question.
David J. Haglin (1992) studied this question.