You are in : Home » Results & submissions » Select UOA » 11 - Computer Science and Informatics » View submission: University of Oxford » Outputs » Detail

Output details

11 - Computer Science and Informatics

University of Oxford

Return to search Previous output Next output

Output 0 of 0 in the submission

Article title

An Algebraic Theory of Complexity for Discrete Optimization

Type

D - Journal article

DOI

10.1137/130906398

Title of journal

SIAM Journal on Computing

Article number

Volume number

Issue number

First page of article

1915

ISSN of journal

0097-5397

Year of publication

2013

URL

http://epubs.siam.org/doi/abs/10.1137/130906398

Number of additional authors

Additional information

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

Interdisciplinary

Cross-referral requested

Research group

None

Citation count

Proposed double-weighted

Double-weighted statement

Reserve for a double-weighted output

Non-English

English abstract