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...

Full description

Saved in:
Bibliographic Details
Main Author: LAU, Hoong Chuin
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2002
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/76
https://ink.library.smu.edu.sg/context/sis_research/article/1075/viewcontent/constraints.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1075
record_format dspace
spelling sg-smu-ink.sis_research-10752018-05-18T07:06:21Z A New Approach for Weighted Constraint Satisfaction LAU, Hoong Chuin 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. 2002-04-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/76 info:doi/10.1023/a:1015157615164 https://ink.library.smu.edu.sg/context/sis_research/article/1075/viewcontent/constraints.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Artificial Intelligence and Robotics Business Operations Research, Systems Engineering and Industrial Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Artificial Intelligence and Robotics
Business
Operations Research, Systems Engineering and Industrial Engineering
spellingShingle Artificial Intelligence and Robotics
Business
Operations Research, Systems Engineering and Industrial Engineering
LAU, Hoong Chuin
A New Approach for Weighted Constraint Satisfaction
description 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.
format text
author LAU, Hoong Chuin
author_facet LAU, Hoong Chuin
author_sort LAU, Hoong Chuin
title A New Approach for Weighted Constraint Satisfaction
title_short A New Approach for Weighted Constraint Satisfaction
title_full A New Approach for Weighted Constraint Satisfaction
title_fullStr A New Approach for Weighted Constraint Satisfaction
title_full_unstemmed A New Approach for Weighted Constraint Satisfaction
title_sort new approach for weighted constraint satisfaction
publisher Institutional Knowledge at Singapore Management University
publishDate 2002
url https://ink.library.smu.edu.sg/sis_research/76
https://ink.library.smu.edu.sg/context/sis_research/article/1075/viewcontent/constraints.pdf
_version_ 1770568872670265344