Library

Algebraic Properties of Valued Constraint Satisfaction Problem

The paper presents an algebraic framework for optimization problems expressible as Valued Constraint Satisfaction Problems. Our results generalize the algebraic framework for the decision version (CSPs) provided by Bulatov et al. [SICOMP 2005].

Computer ScienceMathematics
View graphSource

Paper

References (31)

01The Complexity of Valued Constraint SatisfactionP. Jeavons, A. Krokhin, Stanislav Živný2014 · Bull. EATCS · 40 citations
02The Power of Linear Programming for General-Valued CSPsVladimir Kolmogorov, Johan Thapper, Stanislav Živný2013 · SIAM journal on computing (Print) · 89 citations
03Robust Satisfiability for CSPs: Hardness and Algorithmic ResultsV. Dalmau, A. Krokhin2013 · TOCT · 45 citations
04The complexity of finite-valued CSPsJohan Thapper, Stanislav Živný2013 · Symposium on the Theory of Computing · 110 citations
05Skew Bisubmodularity and Valued CSPsAnna Huber, A. Krokhin, Robert Powell2013 · SIAM journal on computing (Print) · 48 citations
06An Algebraic Theory of Complexity for Discrete OptimizationDavid A. Cohen, Martin C. Cooper, Páidí Creed et al.2012 · SIAM journal on computing (Print) · 59 citations
07Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction ProblemL. Barto, M. Kozik2012 · Log. Methods Comput. Sci. · 163 citations In Library
08The complexity of conservative valued CSPsVladimir Kolmogorov, Stanislav Živný2011 · JACM · 71 citations
09Complexity of conservative constraint satisfaction problemsA. Bulatov2011 · TOCL · 155 citations
10Universal algebra and hardness results for constraint satisfaction problemsB. Larose, Pascal Tesson2007 · Theoretical Computer Science · 95 citations
11An Algebraic Characterisation of Complexity for Valued ConstraintDavid A. Cohen, Martin C. Cooper, P. Jeavons2006 · International Conference on Principles and Practice of Constraint Programming · 53 citations
12The complexity of soft constraint satisfactionDavid A. Cohen, Martin C. Cooper, P. Jeavons et al.2006 · Artificial Intelligence · 141 citations

Scroll for more · 19 remaining

Similar papers

Valued Constraint Satisfaction ProblemsMartin C. Cooper, S. D. Givry, T. Schiex2020 · A Guided Tour of Artificial Intelligence Research · 6 citations In Library
Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of VariablesM. Bodirsky, M. Mamino, C. Viola2020 · AIRO Springer Series · 0 citations In Library
Binarisation for Valued Constraint Satisfaction ProblemsDavid A. Cohen, Martin C. Cooper, P. Jeavons et al.2016 · SIAM Journal on Discrete Mathematics · 6 citations In Library
Hybrid tractability of soft constraint problemsMartin C. Cooper, Stanislav Živný2010 · Artificial Intelligence · 49 citations In Library
A Complexity Dichotomy for Temporal Valued Constraint Satisfaction ProblemsM. Bodirsky, '. Bonnet, vZaneta Semanivsinov'a2024 · 1 citation In Library
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite DomainsM. Bodirsky, M. Mamino, C. Viola2018 · Annual Conference for Computer Science Logic · 3 citations In Library
The Complexity of Resilience Problems via Valued Constraint Satisfaction ProblemsM. Bodirsky, Žaneta Semanišinová, Carsten Lutz2023 · Logic in Computer Science · 5 citations In Library
Quantaloidal approach to constraint satisfactionSoichiro Fujii, Yuni Iwamasa, Kei Kimura2021 · ACT · 1 citation In Library
Binarisation via Dualisation for Valued ConstraintsDavid A. Cohen, Martin C. Cooper, P. Jeavons et al.2015 · AAAI Conference on Artificial Intelligence · 6 citations In Library
A categorical perspective on constraint satisfaction: The wonderland of adjunctionsMaximilian Hadek, Tomás Jakl, Jakub Opršal2025 · arXiv.org · 3 citations In Library
© 2026 NYSGPT2525 LLC