Skew Bisubmodularity and Valued CSPs

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

zbMATH Keywords

optimizationcomputational complexitysubmodularitydichotomyvalued constraint satisfaction problem

Mathematics Subject Classification ID

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