The power of linear programming for general-valued CSPs

Vladimir Kolmogorov, Johan Thapper, Stanislav Zivny

Let $D$, called the domain, be a fixed finite set and let $\Gamma$, called the valued constraint language, be a fixed set of functions of the form $f:D^m\to \mathbb{Q}\cup \{\infty \}$, wh…