Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

DOI10.1145/3488721OpenAlexW3214912144WikidataQ130872036 ScholiaQ130872036MaRDI QIDQ5056366FDOQ5056366

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

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

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)

Cited In (4)

• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
• The power of linear programming for general-valued CSPs
• 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)