The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains

DOI10.1145/3458041MaRDI QIDQ5032030zbMATH OpenOpenAlexFDO

Authors C. Viola, S. Zivny

Publication date 16 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.01779, https://drops.dagstuhl.de/opus/volltexte/2020/12756/

zbMATH Keywords

polymorphismsconvex relaxationsvalued constraint satisfactionpromise constraint satisfaction

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• The power of linear programming for general-valued CSPs

Cited in

(6)

• The complexity of resilience problems via valued constraint satisfaction problems
• Algebraic approach to approximation
• On classifying continuous constraint satisfaction problems
• A duality approach to regularized learning problems in Banach spaces
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems

This page was built for publication: The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032030)