Output details
11 - Computer Science and Informatics
University of Durham
Article title
The approximability of MAX CSP with fixed-value constraints.
Type
D - Journal article
Title of journal
Journal of the ACM
Article number
16
Volume number
55
Issue number
4
First page of article
-
ISSN of journal
0004-5411
Year of publication
2008
Number of additional authors
3
Additional information
<12>This paper highlighted the role of specific algebraic properties in classifying the complexity of Max CSPs. Subsequent research in this direction led to very general classification results by Kolmogorov and Zivny (SODA 2012) and Thapper and Zivny (FOCS 2012), and eventually to a full complexity classification of constraint optimisation problems by Thapper and Zivny (STOC 2013). The above mentioned results generalise the complexity, but not the approximability part of my result.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Algorithms and Complexity Research Group
Citation count
15
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
