The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP

DOI10.1007/978-3-319-59776-8_31zbMath1489.68262OpenAlexW2618012076MaRDI QIDQ2011611

Sven Koenig, T. K. Satish Kumar, Hong Xu

Publication date: 4 August 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-59776-8_31

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Uses Software

• DARN!
• CP-nets
• Gurobi
• Boost
• BGL

Cites Work

• Unnamed Item
• Unnamed Item
• DARN! A weighted constraint solver for RNA motif localization
• Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
• Multi-language evaluation of exact solvers in graphical model discrete optimization
• A New Solver for the Minimum Weighted Vertex Cover Problem
• Information, Physics, and Computation
• A new approach to the maximum-flow problem
• Vertex packings: Structural properties and algorithms
• Convergence of Min-Sum Message-Passing for Convex Optimization