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

Published

Standard

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

Harvard

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

APA

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

Vancouver

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

Author

Cohen, David A. ; Cooper, Martin C. ; Creed, Páidí ; Jeavons, Peter G. ; Živný, Stanislav. / An Algebraic Theory of Complexity for Discrete Optimisation. In: SIAM Journal on Computing. 2013 ; Vol. 42, No. 5. pp. 1915-1939.

BibTeX

@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",

}

RIS

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 -