Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
Article title
An Algebraic Theory of Complexity for Discrete Optimisation
Type
D - Journal article
Title of journal
SIAM Journal on Computing
Article number
-
Volume number
42
Issue number
5
First page of article
1915
ISSN of journal
0097-5397
Year of publication
2013
Number of additional authors
4
Additional information
<12>Our earlier work, showing that weighted polymorphisms characterize the complexity of CSP with optimization, produced the understanding of the complexity of optimization which lead to the work in this paper. The initial work, on the complexity of classical CSP languages, has been enormously influential. The natural closure operator for weighted polymorphisms, presented in this paper, provides a theoretical underpinning, allowing the possibility of properly understanding the complexity of optimization. It is already proving to be as influential as the earlier work. For example, it has been a key topic at international meetings in Dagstuhl (2012) and Vancouver (2013)
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Centre for Algorithms and their Applications
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
