AbstractWe 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.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search; F.1.3 [Computation by Abstract Devices]: Complexity Classes
Additional Key Words and Phrases: approximation algorithms, constraint satisfaction problem, randomized rounding
Selected references
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 733-744, Victoria, British Columbia, Canada, 4-6 May 1992.
- Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science, 134(2):545-557, 21 November 1994. Note.
- Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.
- Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. In 35th Annual Symposium on Foundations of Computer Science, pages 819-830, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Sanjeev Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In 36th Annual Symposium on Foundations of Computer Science, pages 162-169, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425-440, December 1991.
- Ran Raz. A parallel repetition theorem. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 447-456, Las Vegas, Nevada, 29 May-1 June 1995.
- R. J. Wallace and E. C. Freuder. Conjunctive width heuristics for maximal constraint satisfaction. In Proceedings of the 11th National Conference on Artificial Intelligence, pages 762-768, Washington, DC, July 1993. AAAI Press.