Some optimal inapproximability results
Some optimal inapproximability results
复制标题
DOI：
10.1145/502090.502098
复制
发表时间：
2001-07-01
影响因子：
2.5
通讯作者：
Håstad, J
中科院分区：
文献类型：
--
作者：
Håstad, J
我们证明了最优的，直到任意的ε> 0，Max-Ek-Sat的不可逼近性结果，k大于或等于3，最大化满足的线性方程组的数量在一个超定系统的线性方程组模素数p和集分裂。作为这些结果的结果，我们得到了许多优化问题的有效逼近以前研究的改进下界。特别是对于Max-E2-Sat、Max-Cut、Max-di-Cut和Vertex cover。
We prove optimal, up to an arbitrary epsilon > 0, inapproximability results for Max-Ek-Sat for k greater than or equal to 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.