<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-22T21:24:38.733Z
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”?
j.s.
CC BY-SA 3.0
2011-09-22T21:49:11.910Z
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.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-09-22T18:14:22.720Z
2011-09-22T18:38:22.543Z
2011-09-22T18:38:22.543Z
Mahdi Cheraghchi
<p>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 <a href="http://en.wikipedia.org/wiki/Cut_%28graph_theory%29#Sparsest_cut" rel="nofollow">sparsest-cut</a>) by reduction from PCPs?</p>

<p>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.</p>

<cc.complexity-theory><approximation-hardness><csp><pcp>
hardness of approximation result for a Min-CSP, by reduction from PCPs
j.s.
# hardness of approximation result for a Min-CSP, by reduction from PCPs

(Asked by: username_0 on 2011-09-22)

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](http://en.wikipedia.org/wiki/Cut_%28graph_theory%29#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.

**Tags:** cc.complexity-theory, approximation-hardness, csp, pcp

---

## 1 answers

### Answer by username_1 on 2011-09-22. Score: 4

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.

> **Comments:**
> **username_0**: 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”?  
> **username_1**: 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.  

---

