Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

DOI10.1145/3488721MaRDI QIDQ5056366zbMATH OpenOpenAlexWikidataFDO

Authors Manuel Bodirsky, Marcello Mamino, C. Viola

Publication date 8 December 2022

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

submodularitypiecewise linear functionslinear programming relaxationvalued constraint satisfactionrational domain

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Piecewise linear valued constraint satisfaction problems with fixed number of variables
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of linear programming for general-valued CSPs

Cited in

(6)

• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of linear programming for general-valued CSPs
• Submodular functions and valued constraint satisfaction problems over infinite domains
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
• Piecewise linear valued constraint satisfaction problems with fixed number of variables

This page was built for publication: Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

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