The complexity of finitevalued CSPs
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Dr Thomas Sauerwald.
Let L be a set of rationalvalued functions on a fixed finite domain; such a set is called a finitevalued 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 finitevalued 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 MaxCut.
(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:
Note that exdirectory lists are not shown.
