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.
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.
| Item Type: | Article |
|---|---|
| Keywords: | Supermodular function, Lattices, Optimization, Tractability, Constraint satisfaction. |
| Full text: | (VoR) Version of Record Download PDF (236Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.1137/060669565 |
| Publisher statement: | © 2008 Society for Industrial and Applied Mathematics |
| Date accepted: | No date available |
| Date deposited: | 05 January 2010 |
| Date of first online publication: | February 2008 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
