University of Cambridge > Talks.cam > Cambridge Algorithms talks > The complexity of finite-valued CSPs

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

The complexity of finite-valued CSPs

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 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:

Note that ex-directory lists are not shown.

Other lists

ld636 The Winstanley Lecture Theatre, Trinity College, Cambridge St John's Church Hall, Hills Road, opposite Homerton

Other talks

Caribbean Trip and Cacti Group Work Content, Caching and Kubernetes: Performance and User Experience in the Browser Market Failure, Organ Shortage, Pandemic and Climate Change: The Architecture of Cooperation TBC Title TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity