Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

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:PDF - Published Version (236Kb)
Status:Peer-reviewed
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: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library