Output details
11 - Computer Science and Informatics
University of Oxford
An Algebraic Theory of Complexity for Discrete Optimization
<10>
This paper extends the powerful algebraic theory previously developed for constraint satisfaction problems to the much more general framework of discrete optimisation problems known as "constraint optimisation problems" or "optimisation problems with valued constraints". One anonymous reviewer commented that "The generalization of the CSP theory to the valued CSP is by no means straightforward. ... The result promises a boom of results about VCSPs ... and it also opens new algebraic research directions. There are already at least two strong recent results which rely on the theory developed in this paper."
This 26-page journal paper builds on conference papers presented at CP2006 (15 pages), MFCS2011 and CP2011. In particular, it introduces the notion of "weighted polymorphism" which supersedes the algebraic tools used in the CP2006 paper. None of this work was submitted to RAE2008.