Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.

DOI10.4230/LIPIcs.STACS.2018.39zbMath1454.68059OpenAlexW2791542800MaRDI QIDQ3304138

Stanislav Živný, Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota

Publication date: 5 August 2020

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.39

zbMATH Keywords

discrete convex analysisvalued constraint satisfaction problemsM-convexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

A Tractable Class of Binary VCSPs via M-Convex Intersection

Cites Work

• Hybrid tractability of valued constraint problems
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Valuated matroids
• Discrete convex analysis
• Discrete convexity in joint winner property
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A geometric study of the split decomposition
• Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
• Recent Developments in Discrete Convex Analysis
• Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
• Discrete Convex Analysis
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• The Complexity of Valued Constraint Satisfaction Problems
• A Tractable Class of Binary VCSPs via M-Convex Intersection
• Hybrid Tractable Classes of Constraint Problems
• The Power of Linear Programming for General-Valued CSPs
• The Complexity of General-Valued CSPs
• Matrices and matroids for systems analysis
• Discrete convexity and polynomial solvability in minimum 0-extension problems