2026-07-21T23:17:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24385 2025-12-12T15:01:19Z ddc:004 open_access

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems DeHaan, Ian Huang, Neng Lee, Euiwoong Constraint satisfaction problems approximation algorithms polymorphisms 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ian DeHaan and Neng Huang and Euiwoong Lee 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.19 urn:nbn:de:0030-drops-243851 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode