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.