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 journalArticlepeer-review



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