2
$\begingroup$

Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for Max-CSPs? In other words, can someone get hardness of approximation result for a Min-CSP (for example, Vertex-Cover or sparsest-cut) by reduction from PCPs?

If it is always possible to convert a Min-CSP to an equivalent Max-CSP, then maybe this answers my question. But, I don’t know whether it is always possible or not.

$\endgroup$

1 Answer 1

4
$\begingroup$

One reason we see Max-CSPs more is that they often capture convex optimization problems for which minimization is easy (e.g., Max-CUT vs Min-CUT).

A Min-CSP is equivalent to a Max-CSP when you negate all the constraints. So minimization and maximization are equivalent if you're asking for the optimum solution. But this reduction is not approximation preserving in the sense that, say, a constant factor approximation of the negated CSP does not necessarily imply a constant factor approximation of the original CSP. Approximation of Max-CSPs and Min-CSPs can however be studied under the unified framework of "generalized CSPs", when constraints have weights and can be fractionally satisfied. Prasad Raghavendra's thesis is a good resource about this.

The specific problem of Vertex-Cover is not really a CSP in the standard sense. However the approximation of the problem is captured by the so-called "free-bit complexity" of PCPs. See "Free bits, PCPs and non-approximability -- towards tight results" by Bellare, Goldreich, and Sudan.

$\endgroup$
2
  • $\begingroup$ Thanks for your helpful answer. Would you give me some References or examples for your claim that “your MaxCSP-to-MinCSP reduction is not approximation-preserving”? $\endgroup$
    – j.s.
    Commented Sep 22, 2011 at 21:24
  • 3
    $\begingroup$ Well, suppose you have a Min-CSP with optimum value OPT. Say you negate the constraints to obtain a Max-CSP with optimum value 1-OPT, and use an alpha-approximation algorithm (alpha < 1) to satisfy alpha(1-OPT) fraction of the constraints. This way you obtain an OPT/(1-alpha(1-OPT)) factor approximation for your original Min-CSP which can be bad if OPT is small, unless alpha is asymptotically 1. $\endgroup$ Commented Sep 22, 2011 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.