BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T022128Z
UID:Seminar-dept-343@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20140218T160000
DTEND:20140218T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Stanislav Zivny: The complexity of finite-valued CSPs\n\nLet L be a set of rational-valued functions on a fixed finite domain; such a set\n\nis called a finite-valued constraint language. We are interested in the problem\n\nof minimising a function given explicitly as a sum of functions from L. We\n\nestablish a dichotomy theorem with respect to exact solvability for all\n\nfinite-valued languages defined on domains of arbitrary finite size. We present\n\na simple algebraic condition that characterises the tractable cases. Moreover,\n\nwe show that a single algorithm based on linear programming solves all tractable\n\ncases. Furthermore, we show that there is a single reason for intractability;\n\nnamely, a very specific reduction from Max-Cut.\n\n\n\n(based on work published at FOCS'12 and STOC'13, joint work with J. Thapper)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=343
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR