## 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 |