Randomized approximation of the constraint satisfaction problem (Q4375640)

We give an improved approximation of the Weighted Constraint Satisfaction Problem (W-CSP) using randomized rounding introduced by \textit{P. Raghavan} and \textit{C. D. Thompson} [Combinatorica 7, 365-374 (1987; Zbl 0651.90052)]. The key idea is to formulate our problem as an integer program, solve a convex mathematical programming relaxation (such as a linear program), treat the values of the optimal fractional solution as a probability distribution and obtain an integer solution using this distribution. Raghavan and Thompson showed that the values chosen under the distribution do in fact yield a solution near the expectation, thus giving good approximate solutions to the integer program. This technique yields a randomized algorithm, which can be derandomized using the method of conditional probabilities. We are mainly concerned with binary constraints (i.e. arity 2 problems), although some of our results can be easily extended to higher arities. Unless otherwise stated, W-CSP will now refer to the class of instances with binary constraints. Our contributions are as follows: (1) By interactive proofs, we show that W-CSP in general has no \(O(\log n)\) approximation ratio, even if the underlying constraint graph is bipartite, unless EXP=NEXP. (2) By representing W-CSP as a linear integer program and applying randomized rounding to its linear program relaxation, we obtain an approximation ratio of \(1/(2k)+ s/4\), where \(s\) is the weighted average strength of the constraints. The ratio can be improved to \(1/k^{t- 1}\) for satisfiable instances of arity \(t\). These ratios are best possible in the sense that there exist instances whose expected weights match the ratios exactly. (3) By a simple rounding scheme to a semidefinite program relaxation, we obtain a constant-approximation of 0.408 for the case of \(k\leq 3\). This ratio is tight in the sense that, regardless of the rounding scheme, there exists an instance whose expected weight is no more than 0.5 times the optimal value. We also analyze the hyperplane-rounding method of Goemans and Williamson for the case \(k= 2\) and derive a ratio of 0.634, which can be improved to 0.878 in two special cases. For the entire collection see [Zbl 0851.00083].