Publication Type
Journal Article
Version
publishedVersion
Publication Date
4-2002
Abstract
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.
Discipline
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Constraints
Volume
7
Issue
2
First Page
151
Last Page
165
ISSN
1383-7133
Identifier
10.1023/a:1015157615164
Publisher
Springer Verlag
Citation
LAU, Hoong Chuin.
A New Approach for Weighted Constraint Satisfaction. (2002). Constraints. 7, (2), 151-165.
Available at: https://ink.library.smu.edu.sg/sis_research/76
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1023/a:1015157615164
Included in
Artificial Intelligence and Robotics Commons, Business Commons, Operations Research, Systems Engineering and Industrial Engineering Commons