Krokhin, A. and Larose, B. (2008) 'Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction.', SIAM journal on discrete mathematics., 22 (1). pp. 312-328.
Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a supermodular function which is defined on a product of $n$ copies of a fixed finite lattice and given by an oracle. We exhibit a large class of finite lattices for which this problem can be solved in oracle-polynomial time in $n$. We also obtain new large classes of tractable maximum constraint satisfaction problems.
|Keywords:||Supermodular function, Lattices, Optimization, Tractability, Constraint satisfaction.|
|Full text:||PDF - Published Version (236Kb)|
|Publisher Web site:||http://dx.doi.org/10.1137/060669565|
|Publisher statement:||© 2008 Society for Industrial and Applied Mathematics|
|Record Created:||18 Dec 2009 11:05|
|Last Modified:||06 Dec 2011 09:43|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|