Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS semianr by Stanislav Zivny: The complexity of finite-valued CSPs

LFCS semianr by Stanislav Zivny: The complexity of finite-valued CSPs

— filed under:

The complexity of finite-valued CSPs Stanislav Zivny (Oxford) (based on work published at FOCS'12 and STOC'13, joint work with J. Thapper)

What
  • LFCS Seminar
When Feb 25, 2014
from 04:00 PM to 05:00 PM
Where IF 4.31-4.33
Contact Name Ilias Diakonikolas
Add event to calendar vCal
iCal

 

Abstract:

Let L be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. We are interested in the problem of minimising a function given explicitly as a sum of functions from L. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size. We present a simple algebraic condition that characterises the tractable cases. Moreover, we show that a single algorithm based on linear programming solves all tractable cases. Furthermore, we show that there is a single reason for intractability; namely, a very specific reduction from Max-Cut.

Document Actions