Please use this identifier to cite or link to this item: https://doi.org/10.1023/A:1015157615164
Title: A new approach for weighted constraint satisfaction
Authors: Lau, H.C. 
Keywords: Approximation algorithm
Constraint satisfaction
Randomization
Semidefinite programming
Issue Date: 2002
Source: Lau, H.C. (2002). A new approach for weighted constraint satisfaction. Constraints 7 (2) : 151-165. ScholarBank@NUS Repository. https://doi.org/10.1023/A:1015157615164
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.
Source Title: Constraints
URI: http://scholarbank.nus.edu.sg/handle/10635/38975
ISSN: 13837133
DOI: 10.1023/A:1015157615164
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Dec 12, 2017

Page view(s)

49
checked on Dec 8, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.