{"ID":6536175,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10667","arxiv_id":"2607.10667","title":"Constant-factor approximation of MinCostCSP with a conservative majority polymorphism","abstract":"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 variable-value pairs, find a solution to the instance minimizing the sum of the chosen costs. For the exact minimization, a classification of MinCostCSP(A) in terms of A was established by Takhanov [STACS'10]. We focus on constant-factor approximations of MinCostCSP(A). DeHaan, Huang, and Lee recently showed that if A fails to admit a conservative near-unanimity polymorphism then MinCostCSP(A) is not constant-factor approximable [APPROX'25]. We provide a first step towards a classification, by proving a dichotomy for structures A admitting a conservative majority (also known as 3-near-unanimity) polymorphism. Our dichotomy criterion is not in terms of an algebraic condition on A but we show that this is unavoidable. We include a simple argument proving that no such condition exists.","short_abstract":"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 variable-value pairs, find a solution to the instance minimizing the sum of the chosen costs. For the exact minimization, a classification...","url_abs":"https://arxiv.org/abs/2607.10667","url_pdf":"https://arxiv.org/pdf/2607.10667v1","authors":"[\"Marcin Kozik\",\"Stanislav Živný\"]","published":"2026-07-12T09:24:44Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}