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

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

zbMATH Keywords

optimisationconstraint satisfactionmodel theorypiecewise linear functionssemilinearsubmodular functionsvalued constraint satisfaction problems

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• The power of linear programming for general-valued CSPs
• Algebraic properties of valued constraint satisfaction problem
• Min CSP on four elements: moving beyond submodularity

Cited In (1)

• On the Nisan-Ronen conjecture for submodular valuations

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)