The approximability of non-Boolean satisfiability problems and restricted integer programming

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.