文章基本信息

标题：On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
本地全文：下载
作者：Per Austrin ; Rajsekar Manokaran ; Cenny Wenner 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2015
卷号：11
页码：257-283
出版社：University of Chicago
摘要：We show improved $\mathsf{NP}$-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove $\mathsf{NP}$-hard approximation factors of ${14}/{15}+\varepsilon$ and ${1}/{2}+\varepsilon$. When it is hard to approximate an OCSP by a constant better than taking a uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show that the Maximum Non- Betweenness Problem is approximation resistant and that there are width-$m$ approximation-resistant OCSPs accepting only a fraction $1 / (m/2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to $\mathsf{P} \neq \mathsf{NP}$
关键词：acyclic subgraph; APPROX; approximation; approximation resistance; betweenness; constraint satisfaction; CSPs; feedback arc set; hypercontractivity; NP-completeness; orderings; PCP; probabilistically checkable proofs