An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains

DOI10.1016/j.jmaa.2022.126591OpenAlexW4291226848WikidataQ124801085 ScholiaQ124801085MaRDI QIDQ2674328

Caterina Viola, Friedrich Martin Schneider

Publication date: 23 September 2022

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.04912

zbMATH Keywords

locally convex spacesexpressive powerFarkas' lemmavalued constraint satisfactioninfinite-domain valued structures

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Theory of computing (68Qxx) Algebraic structures (08Axx)

Cites Work

• Unnamed Item
• Unnamed Item
• Correlation clustering
• A new polynomial-time algorithm for linear programming
• A general Farkas lemma
• A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
• The Complexity of Finite-Valued CSPs
• Algebraic Properties of Valued Constraint Satisfaction Problem
• Non-dichotomies in Constraint Satisfaction Complexity
• A Galois Connection for Weighted (Relational) Clones of Infinite Size
• Constraint Satisfaction Problems over Numeric Domains
• The Complexity of Valued CSPs
• Reducibility among Combinatorial Problems
• Classifying the Complexity of Constraints Using Finite Algebras
• An Algebraic Theory of Complexity for Discrete Optimization

This page was built for publication: An application of Farkas' lemma to finite-valued constraint satisfaction problems over infinite domains