Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Constant-factor approximation of MinCostCSP with a conservative majority polymorphism
Marcin Kozik, Stanislav Živný
For a relational structure A, the Minimum Cost Constraint Satisfaction Problem is the following problem denoted by MinCostCSP(A): Given an instance of CSP(A) with rational costs on…
cs.CC2024
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
Libor Barto, Zarathustra Brady, Andrei Bulatov +2
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend p…