1996 | ReviewPaper | Buchkapitel
A new approach for Weighted Constraint Satisfaction: Theoretical and computational results
verfasst von : Hoong Chuin Lau
Erschienen in: Principles and Practice of Constraint Programming — CP96
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the Weighted Constraint Satisfaction Problem which is a central 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, our algorithm is simple and efficient in practice, and produces better solutions than other polynomial-time algorithms such as greedy and randomized local search.