An Algebraic Theory of Complexity for Discrete Optimisation. / Cohen, David A.; Cooper, Martin C.; Creed, Páidí; Jeavons, Peter G.; Živný, Stanislav.

In: SIAM Journal on Computing, Vol. 42, No. 5, 2013, p. 1915-1939.

Research output: Contribution to journalArticle



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.
Original languageEnglish
Pages (from-to)1915-1939
Number of pages24
JournalSIAM Journal on Computing
Issue number5
Publication statusPublished - 2013
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 16831398