Abstract
Discrete optimisation problems arise in many different areas and are studied under many different
names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted
form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a
finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function,
which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions
and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised.
These results provide a new approach to studying the complexity of discrete optimisation. We use this approach
to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification
of complexity for the Boolean case.
names. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restricted
form. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of a
finite-domain discrete optimisation problem is determined by certain algebraic properties of the objective function,
which we call weighted polymorphisms. We define a Galois connection between sets of rational-valued functions
and sets of weighted polymorphisms and show how the closed sets of this Galois connection can be characterised.
These results provide a new approach to studying the complexity of discrete optimisation. We use this approach
to identify certain maximal tractable subproblems of the general problem, and hence derive a complete classification
of complexity for the Boolean case.
| Original language | English |
|---|---|
| Pages (from-to) | 1915-1939 |
| Number of pages | 24 |
| Journal | SIAM Journal on Computing |
| Volume | 42 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 2013 |