Randomized approximation of the constraint satisfaction problem

• Main Authors: LAU, Hoong Chuin, WATANABE, Osamu
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 1996
• Subjects: Approximation algorithms; constraint satisfaction problem; randomized rounding; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/150; https://ink.library.smu.edu.sg/context/sis_research/article/1149/viewcontent/Randomized_approximation_of_the_constraint_pv.pdf
• Institution: Singapore Management University

We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approximations of W-CSP via randomized rounding of linear programming and semidefinite programming relaxations. Our algorithms are simple to implement and experiments show that they are run-time efficient.