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?


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.