Supermodularity on chains and complexity of maximum constraint satisfaction

MaRDI QIDQ3576659zbMATH OpenFDO

Authors Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei Krokhin

Publication date 30 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAE0111/0.html

zbMATH Keywords

complexitysupermodularitymaximum constraint satisfactionMonge propertiesdigraph H -colouring

Mathematics Subject Classification ID

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

Recommendations

• Supermodular functions and the complexity of MAX CSP
• STACS 2004
• The approximability of MAX CSP with fixed-value constraints
• Maximum Constraint Satisfaction on Diamonds
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction

Cited in

(10)

• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Supermodular programming on lattices
• Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• The approximability of MAX CSP with fixed-value constraints
• STACS 2004
• Supermodular functions and the complexity of MAX CSP
• Classes of submodular constraints expressible by graph cuts
• Minimum cost and list homomorphisms to semicomplete digraphs

This page was built for publication: Supermodularity on chains and complexity of maximum constraint satisfaction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576659)