Report icon

Report

Supermodular Functions and the Complexity of MAX CSP

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. We describe for the first time a general approach to the question of classifying the complexity of Max C...

Expand abstract

Actions


Authors


Publisher:
Oxford University Computing Laboratory
Publication date:
2004-01-01
URN:
uuid:1c7c54f8-d3d9-497a-9bc6-dba4d8f57ab0
Local pid:
cs:24

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP