标题： 关于最小成本约束满足问题的常数因子近似性 显示英文标题

标题： On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

摘要： 我们通过代数的视角研究最小成本约束满足问题（MinCostCSP）。 我们证明，对于任何具有对偶歧视操作作为多态性的约束语言$\Gamma$，存在一个$|D|$近似算法用于 MinCostCSP$(\Gamma)$，其中$D$是域。 在我们的算法结果之外，我们证明，任何约束语言$\Gamma$，如果 MinCostCSP$(\Gamma)$可以进行常数因子近似，则必须具有\emph{几乎一致}（NU）多态性，除非 P = NP，这扩展了 Dalmau 等人关于 MinCSP 的类似结果。 这些结果表明，包含所有排列关系的约束语言（这是允许变量否定的布尔CSP的一种自然推广）在常数因子近似性方面存在二分法：要么MinCostCSP$(\Gamma)$具有NU多项式，并且是$|D|$-近似可解的，要么它不具有任何NU多项式，并且在任何常数因子内近似求解都是NP难的。 最后，我们提出一个具有多数多项式的约束语言，但在假设唯一游戏猜想成立的情况下，它仍然在任何常数因子内近似求解是NP难的，这表明具有NU多项式的条件在一般情况下并不充分，除非UGC不成立。 显示英文摘要

摘要： We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language $\Gamma$ which has the dual discriminator operation as a polymorphism, there exists a $|D|$-approximation algorithm for MinCostCSP$(\Gamma)$ where $D$ is the domain. Complementing our algorithmic result, we show that any constraint language $\Gamma$ where MinCostCSP$(\Gamma)$ admits a constant-factor approximation must have a \emph{near-unanimity} (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP$(\Gamma)$ has an NU polymorphism and is $|D|$-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.