Randomized approximation of the constraint satisfaction problem

Randomized approximation of the constraint satisfaction problem

We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approxima...

Full description

Saved in:
Bibliographic Details
Main Authors: LAU, Hoong Chuin, WATANABE, Osamu
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 1996
Subjects:
Approximation algorithms
constraint satisfaction problem
randomized rounding
Artificial Intelligence and Robotics
Operations Research, Systems Engineering and Industrial Engineering
Online Access:https://ink.library.smu.edu.sg/sis_research/150
https://ink.library.smu.edu.sg/context/sis_research/article/1149/viewcontent/Randomized_approximation_of_the_constraint_pv.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:We consider the Weighted Constraint Satisfaction Problem (W-CSP) which is a fundamental problem in Artificial Intelligence and a generalization of important combinatorial problems such as MAX CUT and MAX SAT. In this paper, we prove non-approximability properties of W-CSP and give improved approximations of W-CSP via randomized rounding of linear programming and semidefinite programming relaxations. Our algorithms are simple to implement and experiments show that they are run-time efficient.

Similar Items