We study the computational complexity of exact minimization of rational-valued discrete
functions. Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is …

An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of
variables, a finite domain of labels, and a sum of functions, each function depending on a …

In this paper we investigate k-submodular functions. This natural family of discrete functions
includes submodular and bisubmodular functions as the special cases k= 1 and k= 2 …

Let D, called the domain, be a fixed finite set and let Γ, called the valued constraint
language, be a fixed set of functions of the form f:D^m→Q∪{∞\}, where different functions …

A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued
constraint language, a fixed set of cost functions on a finite domain. An instance of the …

We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction
Problems and their Promise variant. The idea is to split the description of a hierarchy into an …

Abstract We consider Markov Decision Processes (MDPs) with mean-payoff parity and
energy parity objectives. In system design, the parity objective is used to encode ω-regular …

We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by
a constraint language, a fixed set of cost functions over a finite domain. An instance of the …

Discrete optimization problems arise in many different areas and are studied under many
different names. In many such problems the quantity to be optimized can be expressed as a …

The topic of this book is the following optimisation problem: given a set of discrete variables
and a set of functions, each depending on a subset of the variables, minimise the sum of the …