The Complexity of finite-valued CSPs

Add to your list(s) Download to your calendar using vCal

• Stanislav Zivny, Department of Computer Science University of Oxford
• Monday 09 June 2014, 10:00-11:00
• FW26, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Dr Thomas Sauerwald.

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.

This talk is part of the Department of Computer Science and Technology talks and seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Department of Computer Science and Technology talks and seminars
• FW26, Computer Laboratory, William Gates Builiding
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.