A New Approach for Weighted Constraint Satisfaction
We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of s...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | text |
| اللغة: | English |
| منشور في: |
Institutional Knowledge at Singapore Management University
2002
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://ink.library.smu.edu.sg/sis_research/76 https://ink.library.smu.edu.sg/context/sis_research/article/1075/viewcontent/constraints.pdf |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| المؤسسة: | Singapore Management University |
| اللغة: | English |
| الملخص: | We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum 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 for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and randomized local search. |
|---|