Publication Type
Journal Article
Version
publishedVersion
Publication Date
1996
Abstract
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.
Keywords
Approximation algorithms, constraint satisfaction problem, randomized rounding
Discipline
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Research Areas
Intelligent Systems and Optimization
Publication
Nordic Journal of Computing
Volume
3
Issue
4
First Page
405
Last Page
424
ISSN
1236-6064
Identifier
10.1007/3-540-61422-2_122
Publisher
Nordic Journal of Computing
Citation
LAU, Hoong Chuin and WATANABE, Osamu.
Randomized approximation of the constraint satisfaction problem. (1996). Nordic Journal of Computing. 3, (4), 405-424.
Available at: https://ink.library.smu.edu.sg/sis_research/150
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/3-540-61422-2_122
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons
Comments
Also published in Lecture Notes in Computer Science, Volume 1097, 1996, Pages 76-87. 5th Scandinavian Workshop on Algorithm Theory, SWAT 1996, Reykjavik, Iceland, 3-5 July 1996. https://doi.org/10.1007/3-540-61422-2_122