Min CSP on Four Elements: Moving beyond Submodularity

DOI10.1007/978-3-642-23786-7_34zbMath1294.68093arXiv1102.2880OpenAlexW1577492601MaRDI QIDQ3169450

Peter Jonsson, Johan Thapper, Fredrik Kuivinen

Publication date: 23 September 2011

Published in: Principles and Practice of Constraint Programming – CP 2011 (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitysubmodularityconstraint satisfaction problemscombinatorial optimisationbisubmodularity

Mathematics Subject Classification ID

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

Related Items

The Complexity of General-Valued CSPs ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ The Complexity of Valued CSPs ⋮ Unnamed Item ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item

This page was built for publication: Min CSP on Four Elements: Moving beyond Submodularity