Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction

DOI10.1137/060669565zbMath1167.90017OpenAlexW2161302568MaRDI QIDQ3614209

Benoit Larose, Andrei A. Krokhin

Publication date: 16 March 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/6287/1/6287.pdf

zbMATH Keywords

optimizationlatticesconstraint satisfactiontractabilitysupermodular function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (9)

The Expressive Power of Binary Submodular Functions ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Colouring, constraint satisfaction, and complexity ⋮ The Complexity of Valued CSPs ⋮ On the complexity of submodular function minimisation on diamonds ⋮ The expressive power of binary submodular functions ⋮ A non-extendibility certificate for submodularity and applications ⋮ Polynomial combinatorial algorithms for skew-bisubmodular function minimization ⋮ The Power of Linear Programming for General-Valued CSPs

This page was built for publication: Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction