BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T102959Z
UID:Seminar-dept-409@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20160510T130000
DTEND:20160510T140000
SUMMARY:School Seminar Series
DESCRIPTION:Prof. Andrei Krokhin: The complexity of general-valued CSPs\n\nAn instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. The case when all functions take only values 0 and infinity corresponds to the standard CSP. We study (assuming that P≠NP) how the complexity of VCSP depends on the set of functions allowed in the instances, the so-called constraint language. Massive progress has been made in the last three years on this complexity classification question, and our work gives, in a way, the final answer to it, modulo the complexity of CSPs.\n\nThis is joint work with Vladimir Kolmogorov and Michal Rolinek (both from IST Austria).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=409
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR