Valued Constraints: Islands of Tractability Dave Cohen Abstract: ======================================================================== In the classical CSP world we have a set of variables and a set of constraints. Each constraint associates a "relation" with a "scope". In the valued CSP framework we instead associates a cost function with each constraint scope. Thus allowing us to consider certain kinds of optimisation problem. We call any set of cost functions a valued constraint language. A classical constraint relation may be seen as a cost function whose only costs are zero and infinity. As such Valued constraint languages properly generalise classical constraint languages and so are NP-hard. We are interested in discovering "islands of tractability". That is, valued constraint languages which define tractable optimisation problems. This talk investigates an algebraic property of valued constraint languages: the multimorphism. We conjecture that the set of multimorphisms of a valued constraint language will determine its expressibility and its complexity in much that same way that the set of polymorphisms do for classical languages. In this talk we give some background to this theory. We will also describe examples which give some justification to our conjecture.