A nice approach suggested by Bliznets and Golovnev [1]} is to
transform solving MaxSAT on a class of special instances into solving
the Set-Cover problem. However, the method proposed in [1]}
is not efficient enough to achieve our bound. For this, we introduce new
branching rules that are sufficiently efficient and further reduce the instances
to an even more restricted form. In particular, we show how to eliminate all
clauses of size bounded by 3. The restricted form of the instances allow us to
apply more powerful techniques in randomized algorithms and in derandomization
[3]} to derive tighter lower bounds on the instances of MaxSAT,
which makes it become possible to use more effectively the existing algorithm for
Set-Cover [4]}.
