Publication Type

Journal Article

Version

Postprint

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

Publication

Nordic Journal of Computing

Volume

3

Issue

4

First Page

405

Last Page

424

ISSN

1236-6064

Publisher

Nordic Journal of Computing

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://dl.acm.org/citation.cfm?id=763878.763886

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. http://doi.org/10.1007/3-540-61422-2_122