Min CSP on Four Elements: Moving Beyond Submodularity

Peter Jonsson, Fredrik Kuivinen, Johan Thapper

We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly…