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

DOI10.1145/3458041OpenAlexW3183881142MaRDI QIDQ5032030FDOQ5032030

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

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
• The complexity of finite-valued CSPs

zbMATH Keywords

polymorphismsconvex relaxationsvalued constraint satisfactionpromise constraint satisfaction

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (3)

• 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

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)