Skew Bisubmodularity and Valued CSPs
From MaRDI portal
Publication:3190693
DOI10.1137/120893549zbMath1360.68512OpenAlexW1983818015MaRDI QIDQ3190693
No author found.
Publication date: 18 September 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/12578/1/12578.pdf
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (12)
Sherali-Adams Relaxations for Valued CSPs ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ On planar valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The Complexity of Valued CSPs ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Generalized skew bisubmodularity: a characterization and a min-max theorem
This page was built for publication: Skew Bisubmodularity and Valued CSPs