3 papers
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.CC2025
The Rise of Plurimorphisms: Algebraic Approach to Approximation
Libor Barto, Silvia Butti, Alexandr Kazda +2
Following the success of the so-called algebraic approach to the study of decision constraint satisfaction problems (CSPs), exact optimization of valued CSPs, and most recently pro…
cs.DS2024
Maximum - vs. -colourings of graphs
Tamio-Vesa Nakajima, Stanislav Živný
We present polynomial-time SDP-based algorithms for the following problem: For fixed , given a real number and a graph that admits a -colouring with a $Ï…