The complexity of finite-valued CSPs

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

• Stanislav Zivny (University of Oxford)
• Monday 09 June 2014, 10:00-11:00
• Computer Laboratory, Room FW26.

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.

(based on work published at FOCS ’12 and STOC ’13, joint work with J.Thapper)

This talk is part of the Cambridge Algorithms talks series.

This talk is included in these lists:

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

Note that ex-directory lists are not shown.