论文标题
关于Max-CSP和Min-CSP的规律性
On Regularity of Max-CSPs and Min-CSPs
论文作者
论文摘要
我们研究常规约束满意度问题的近似性，即CSP，其中一个实例中每个变量的发生数量相同。特别是，我们表明，对于任何CSP $λ$，存在$α$近似算法的未加权常规Max-CSP $λ$的存在意味着存在$α-o（1）$ a $近似算法，用于加权的最大csp $λ$，在这种情况下，没有任何规定的实例。我们还为Min-CSP给出了类似的结果，因此表明，仅在任意小的错误中，仅在常规未加权实例上进行CSP的近似性就足够了。
We study approximability of regular constraint satisfaction problems, i.e., CSPs where each variable in an instance has the same number of occurrences. In particular, we show that for any CSP $Λ$, existence of an $α$ approximation algorithm for unweighted regular Max-CSP $Λ$ implies existence of an $α-o(1)$ approximation algorithm for weighted Max-CSP $Λ$ in which regularity of the instances is not imposed. We also give an analogous result for Min-CSPs, and therefore show that up to arbitrarily small error it is sufficient to conduct the study of approximability of CSPs only on regular unweighted instances.
