Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.


Durham Research Online
You are in:

Supermodular functions and the complexity of MAX CSP.

Cohen, D. and Cooper, M. and Jeavons, P. and Krokhin, A. (2005) 'Supermodular functions and the complexity of MAX CSP.', Discrete applied mathematics., 149 (1-3). pp. 53-72.

Abstract

In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. Using the theory of sub- and supermodular functions on finite lattice-ordered sets, we obtain the first examples of general families of efficiently solvable cases of MAX CSP for arbitrary finite domains. In addition, we provide the first dichotomy result for a special class of non-Boolean MAX CSP, by considering binary constraints given by supermodular functions on a totally ordered set. Finally, we show that the equality constraint over a non-Boolean domain is non-supermodular, and, when combined with some simple unary constraints, gives rise to cases of MAX CSP which are hard even to approximate.

Item Type:Article
Keywords:Constraint satisfaction problem, Optimization, Supermodularity.
Full text:Full text not available from this repository.
Publisher Web site:http://dx.doi.org/10.1016/j.dam.2005.03.003
Record Created:21 Feb 2008
Last Modified:28 Apr 2009 12:04

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library