Approximation Algorithms for Combinatorial Problems II: The Greedy Literal Algorithm B1 Has Worst-Case Ratio (k+1)/k on MS(k)Research Paper
Maximum satisfiability asks for a truth assignment satisfying as many clauses of a propositional formula as possible. The paper notes that the restriction , in which every clause has at least literals, is polynomial complete for every , so exact optimization is out of reach in general and one asks instead how close a fast algorithm is…