Journal article

### An Algebraic Theory of Complexity for Discrete Optimisation

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 Galoi...

Publication status:
Published

### Access Document

Publisher copy:
10.1137/130906398

### Authors

More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Journal:
SIAM Journal on Computing
Volume:
42
Issue:
5
Pages:
1915-1939
Publication date:
2012-07-28
DOI:
EISSN:
1095-7111
ISSN:
0097-5397
URN:
uuid:151cd96c-7b2d-4ab0-8845-3b8890200ec3
Source identifiers:
431443
Local pid:
pubs:431443
Language:
English
Keywords: