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…