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

Research output: Contribution to journal › Article › peer-review

Published

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

Research output: Contribution to journal › Article › peer-review

Cohen, DA, Cooper, MC, Creed, P, Jeavons, PG & Živný, S 2013, 'An Algebraic Theory of Complexity for Discrete Optimisation', *SIAM Journal on Computing*, vol. 42, no. 5, pp. 1915-1939. https://doi.org/10.1137/130906398

Cohen, D. A., Cooper, M. C., Creed, P., Jeavons, P. G., & Živný, S. (2013). An Algebraic Theory of Complexity for Discrete Optimisation. *SIAM Journal on Computing*, *42*(5), 1915-1939. https://doi.org/10.1137/130906398

Cohen DA, Cooper MC, Creed P, Jeavons PG, Živný S. An Algebraic Theory of Complexity for Discrete Optimisation. SIAM Journal on Computing. 2013;42(5):1915-1939. https://doi.org/10.1137/130906398

@article{f345b364c78b4765881780ab7644ced6,

title = "An Algebraic Theory of Complexity for Discrete Optimisation",

abstract = " Discrete optimisation problems arise in many different areas and are studied under many differentnames. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restrictedform. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of afinite-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 functionsand 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 approachto identify certain maximal tractable subproblems of the general problem, and hence derive a complete classificationof complexity for the Boolean case.",

author = "Cohen, {David A.} and Cooper, {Martin C.} and P{\'a}id{\'i} Creed and Jeavons, {Peter G.} and Stanislav {\v Z}ivn{\'y}",

year = "2013",

doi = "10.1137/130906398",

language = "English",

volume = "42",

pages = "1915--1939",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - An Algebraic Theory of Complexity for Discrete Optimisation

AU - Cohen, David A.

AU - Cooper, Martin C.

AU - Creed, Páidí

AU - Jeavons, Peter G.

AU - Živný, Stanislav

PY - 2013

Y1 - 2013

N2 - Discrete optimisation problems arise in many different areas and are studied under many differentnames. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restrictedform. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of afinite-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 functionsand 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 approachto identify certain maximal tractable subproblems of the general problem, and hence derive a complete classificationof complexity for the Boolean case.

AB - Discrete optimisation problems arise in many different areas and are studied under many differentnames. In many such problems the quantity to be optimised can be expressed as a sum of functions of a restrictedform. Here we present a unifying theory of complexity for problems of this kind. We show that the complexity of afinite-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 functionsand 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 approachto identify certain maximal tractable subproblems of the general problem, and hence derive a complete classificationof complexity for the Boolean case.

U2 - 10.1137/130906398

DO - 10.1137/130906398

M3 - Article

VL - 42

SP - 1915

EP - 1939

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 5

ER -