Abstract:
|
We present parallel approximation algorithms for
maximization problems expressible by integer linear programs
of a restricted syntactic form introduced recently by
Barland et al. One of our motivations was to show whether
the approximation results in the framework of Barland et al. holds
in the parallel seeting. Our results are a confirmation of this, and
thus we have a new common framework for both computational settings.
Also, we prove almost tight non-approximability results,
thus solving a main open question of Barland et al.
We obtain the results through the constraint satisfaction problem
over multi-valued domains (which is a natural generalization
of boolean constraint satisfaction and has additional relations
to other problems), for which we show non-approximability
results and develop parallel approximation algorithms.
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 Probastically Checkable Proofs
and Multi-Prover One-Round Proof Systems. |