Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > The complexity of finite-valued CSPs
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

The complexity of finite-valued CSPs

Wednesday 30th April 2014, 4.30pm - 5.30pm
NAB 2.06, LSE

Stanislav Živný

University of Oxford

Personal profile


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.

This is joint work with J. Thapper.

Share:Facebook|Twitter|LinkedIn|

 

Stainslav-Zivny