The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming
The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming
复制标题
非布尔可满足性问题和受限整数规划的（并行）逼近性
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
F. Xhafa
中科院分区：
文献类型：
--
作者：
M. Serna;L. Trevisan;F. Xhafa
我们提出了并行近似算法的最大化问题的整数线性规划的限制的语法形式介绍了Barland等。[BKT 96]。我们的动机之一是要表明是否近似的结果在Barland等人的框架。在平行设置。我们的结果证实了这一点，因此我们有一个新的共同框架，这两个计算设置。此外，我们证明了几乎紧的非逼近结果，从而解决了一个主要的公开问题的Barland等人。我们得到的结果，通过多值域上的约束满足问题，我们显示非逼近的结果，并开发并行逼近算法。我们的并行近似算法是基于线性规划和随机舍入，他们比以前已知的顺序算法。非近似性结果是基于概率可检验证明和多证明者单轮证明系统领域的最新进展[Raz95，Has97，AS97，RS97]。
We present parallel approximation algorithms for maximization problems expressible by integer linear programs of a restricted syntactic form introduced by Barland et al. [BKT96]. One of our motivations was to show whether the approximation results in the framework of Barland et al. holds in the parallel setting. 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, 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 Probabilistically Checkable Proofs and Multi-Prover One-Round Proof Systems [Raz95, Has97, AS97, RS97].