Journal article icon

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

Expand abstract
Publication status:
Published

Actions


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:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP