A Galois Connection for Valued Constraints
    Speaker: 
  
  
  
      Peter Jeavons, University of Oxford  
Date and Time: 
Friday, August 5, 2011 - 9:30am to 10:30am
Abstract: 
The valued CSP is a generalization of the CSP which associates a cost with each possible assignment, and seeks to minimise the total cost. It includes the CSP as a special case (where all costs are either 0 or infinite) but also allows many more discrete optimisation problems to be modelled easily. I will introduce the VCSP and discuss various analogs to the notion of polymorphism that have been developed for analysing its complexity. In particular, I will show that the standard Galois connection given by the functions Pol and Inv can be generalized to the valued case.

