Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction

Krokhin, A.; Larose, B.

doi:10.1137/060669565

Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction

Krokhin, A.; Larose, B.

Authors

Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor

B. Larose

Abstract

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.

Citation

Krokhin, A., & Larose, B. (2008). Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics, 22(1), 312-328. https://doi.org/10.1137/060669565

Journal Article Type	Article
Publication Date	Feb 27, 2008
Deposit Date	Dec 18, 2009
Publicly Available Date	Jan 5, 2010
Journal	SIAM Journal on Discrete Mathematics
Print ISSN	0895-4801
Electronic ISSN	1095-7146
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	22
Issue	1
Pages	312-328
DOI	https://doi.org/10.1137/060669565
Keywords	Supermodular function, Lattices, Optimization, Tractability, Constraint satisfaction.
Publisher URL	http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJDMEC000022000001000312000001&idtype=cvips&gifs=yes