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

Krokhin, A.; Larose, B.

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.
• Public URL: https://durham-repository.worktribe.com/output/1522875
• Publisher URL: http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJDMEC000022000001000312000001&idtype=cvips&gifs=yes