Submodular functions and valued constraint satisfaction problems over infinite domains

DOI10.4230/LIPICS.CSL.2018.12MaRDI QIDQ5079734FDOQ5079734

Authors Manuel Bodirsky, Marcello Mamino, C. Viola 

Publication date 28 May 2022

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

zbMATH Keywords

optimisationconstraint satisfactionmodel theorypiecewise linear functionssemilinearsubmodular functionsvalued constraint satisfaction problems

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• Min CSP on four elements: moving beyond submodularity
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• Item:QQ3177814
• Skew bisubmodularity and valued CSPs

Cites work

• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Algebraic properties of valued constraint satisfaction problem
• Min CSP on four elements: moving beyond submodularity
• The power of linear programming for general-valued CSPs

Cited in

(2)

• On the Nisan-Ronen conjecture for submodular valuations
• Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

This page was built for publication: Submodular functions and valued constraint satisfaction problems over infinite domains

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