We consider tlie Weighted Constraint Satisfaction Problem which is a central problem in Artificial Intelligence. Given a set of vari-ables, their domains and a set of constraints between variables, otir goal is to obtain an assignment of the variables to domain values such that the weighted sura of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds, our algorithm is simple and efficient in practice, and produces better solu-tions than other polynomial-time algorithms such as greedy and random-ized local search.
展开▼
