Let a Boolean formula $\varphi$ in K-CNF with $m$ clauses be given as an input.
The goal of an algorithm is to find an assignment satisfying at least $m(1-2^{-k})$ clauses of $\varphi$.
I need to find:
- A randomized algorithm and estimate its expected time
- A deterministic algorithm and argue about its correctness using the method of conditional expectations
Here are my thoughts about approaching the design of algorithms for this purpose:
Randomized algorithm:
- assigning Boolean values randomly to Boolean variables, counting satisfied clauses
- Finding the expected number of satisfied clauses
- Iterate through as much as is needed
Deterministic algorithm:
- Considering Boolean variables one by one
For a given variable $p$, count how many clauses, that have not been made true yet, are made true by setting $p$ true, and how many by setting $p$ false
Act "greedily"
Does anybody have an example of what such an algorithm would look like in both cases? I don't really have an idea of where to start.