Randomized approximation of the constraint satisfaction problem
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].
- Backtracking and random constraint satisfaction
- How far from a worst solution a random solution of a \(k\) CSP instance can be?
- Approximations and randomization to boost CSP techniques
- Practically uniform solution sampling in constraint programming
- An average analysis of backtracking on random constraint satisfaction problems
- On the freezing of variables in random constraint satisfaction problems
- scientific article; zbMATH DE number 1002207 (Why is no real title available?)
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
- scientific article; zbMATH DE number 5547880 (Why is no real title available?)
- Models for Random Constraint Satisfaction Problems
- Randomized Post-optimization for t-Restrictions
- scientific article; zbMATH DE number 1420826 (Why is no real title available?)
- scientific article; zbMATH DE number 7301529 (Why is no real title available?)
- On the advantage over a random assignment
- Random constraint satisfaction: Flaws and structure
- Branch-and-bound solves random binary IPs in poly(n)-time
- A new approach for weighted constraint satisfaction
- Spines of random constraint satisfaction problems: definition and connection with computational complexity
This page was built for publication: Randomized approximation of the constraint satisfaction problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375640)