Valued constraint satisfaction problems over rational domains

Valued constraint  satisfaction problems, VCSPs, are a wide class of combinatorial optimisation problems. It is interesting to study how the computational complexity of VCSPs depends on the set of allowed cost functions. In the case in which the domain of the cost functions is a finite set, the computational complexity of the VCSPs has been extensively studied and completely characterised.
In the talk, I will present my research that initiates the systematic study of VCSPs for cost functions defined over the rational numbers. I will introduce the class of piecewise linear homogeneous (PLH) cost functions, which is a natural class of cost functions over the rationals that generalises the class of finite-domain VCSPs. I will present a /sampling technique/ to reduce (polynomial-time many-one)  the VCSP for PLH cost functions to a finite-domain  VCSP. Finally, I will present a polynomial-time algorithm for PLH cost functions that have fully symmetric fractional polymorphisms of all arities.
This result generalises a sufficient condition for polynomial-time tractability of finite-domain VCSPs.

(joint work with Manuel Bodirsky and Marcello Mamino)