Publication Type

Journal Article

Publication Date

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 Decision Analytics

Publication

Constraints

Volume

7

Issue

2

First Page

151

Last Page

165

ISSN

1383-7133

Identifier

10.1023/a:1015157615164

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1023/a:1015157615164