Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657922 | Theoretical Computer Science | 2005 | 17 Pages |
Abstract
We obtain the results through the constraint satisfaction problem over multi-valued domains, for which we develop approximation algorithms and show non-approximability results. Our parallel approximation algorithms are based on linear programming and random rounding; they are better than previously known sequential algorithms. The non-approximability results are based on new recent progress in the fields of probabilistically checkable proofs and multi-prover one-round proof systems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Maria Serna, Luca Trevisan, Fatos Xhafa,