2
$\begingroup$

I read this neat result proved in the early 90s:

For any $c>1$, There's a poly time map from boolean formulas $\varphi$ to pairs $K, \mathcal S$ where $K$ is a positive integer and $\mathcal S$ is an instance of set-cover (i.e. $\mathcal S = (U, \{T_1,...,T_n\}\subset 2^U)$) such that

  1. If $\varphi$ is satisfiable, $\mathcal S$ has an exact (i.e pair wise disjoint) cover of size $K$
  2. If $\varphi$ is not satisfiable, $\mathcal S$ has no cover (exact or otherwise) of size smaller than $c\cdot K$.

The result is simple enough but its proof is based on the class MIP which i don't know much about and it's also (for someone of my limited background) strewn across a few different papers.

Has a more straightforward proof been discovered since 1993 or is there somewhere were i can read a more self contained proof of this or approximation results like this?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.