{"ID":2895760,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.08693","arxiv_id":"2507.08693","title":"On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems","abstract":"We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language $Γ$ which has the dual discriminator operation as a polymorphism, there exists a $|D|$-approximation algorithm for MinCostCSP$(Γ)$ where $D$ is the domain. Complementing our algorithmic result, we show that any constraint language $Γ$ where MinCostCSP$(Γ)$ 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$(Γ)$ 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.","short_abstract":"We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language $Γ$ which has the dual discriminator operation as a polymorphism, there exists a $|D|$-approximation algorithm for MinCostCSP$(Γ)$ where $D$ is the domain. Complementing our algorithm...","url_abs":"https://arxiv.org/abs/2507.08693","url_pdf":"https://arxiv.org/pdf/2507.08693v1","authors":"[\"Ian DeHaan\",\"Neng Huang\",\"Euiwoong Lee\"]","published":"2025-07-11T15:46:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.DM\"]","methods":"[]","has_code":false}